Задача D. Мужики и яма ≡

Условие

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

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

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

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

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

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

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

Вторая строка список координат относительно начала балки строителей и их веса: p₁, w₁, ..., p_n, w_n. Координаты рабочих считаются от левого конца балка

Третья строка координаты краёв ям: l₁, r₁, ..., l_k, r_k.

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

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

Ограничения

0 < N * K ≤ 10⁶

0 < l_i, r_i ≤ 10⁹

0 < p_i,  < p_i + 1 ≤ 10⁹

1 < ∑w_i ≤ 10⁹

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

3 1
0 1 1 1 2 1
1 1

0

3 1
0 1 1 3 2 1
1 1

1