O32. Мужики и яма

Автор:Завгороднев А.А. Бадерик П.М.  
Входной файл:Стандартный вход  
Выходной файл:Стандартный выход  

n строителей несут одну балку. И вдруг перед ними оказываются k ям. Строители, не долго думая, двинулись прямиком через эти ямы.

Если вдруг один человек оказался над ямой, то он немедленно вцепляется в балку, а остальные продолжают идти, и таким образом строители пытаются преодолеть ямы (см. картинку).

Но строители не всемогущи, поэтому если в какой-то момент суммарный вес строителей, находящихся над пропастью, превышает суммарный вес строителей, стоящих на земле, то у остальных не хватает сил выдержать висящих на балке, и те падают в яму.

Благо яма не глубокая, поэтому все отделаются легким испугом.

Когда хотя бы один человек падает, все остальные прекращают движение, и ваше наблюдение заканчивается.

Формат входных данных

Первая строка входного файла содержит два числа: n количество строителей, k количество ям.

Вторая строка список координат относительно начала балки строителей и их веса: p1, w1, ..., pn, wn. Координаты рабочих считаются от левого конца балка

Третья строка координаты краёв ям: l1, r1, ..., lk, rk.

Формат выходных данных

Выходной файл должен содержать одно число - количество упавших строителей.

Ограничения

0 < N * K ≤ 106

0 < li, ri ≤ 109

0 < pi, pi + 1 ≤ 109

1 < wi ≤ 109

Примеры тестов

Стандартный вход Стандартный выход
1
3 1
0 1 1 1 2 1
1 1
0
2
3 1
0 1 1 3 2 1
1 1
1

0.134s 0.015s 15