Автор: | Завгороднев А.А. Бадерик П.М. | |||
Входной файл: | Стандартный вход | |||
Выходной файл: | Стандартный выход |
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 |
|
|
2 |
|
|