639. Внезапный шторм

Не решаласьСредняя

Да что же это такое! Новая напасть! Откуда ни возьмись на небе появились серые тучи и начался ливень.

«Это не случайность. Кто-то точно пытается испортить нам праздник...» — задумчиво произносит Кодерун, щурясь в небо.

Впрочем, сейчас важнее понять, насколько сильным будет дождь в ближайшие t t минут.

Метеорологи страны CodeRun уже знают всё о каждой туче: сколько капель воды она содержит и с какой скоростью эта вода будет литься на землю. Сможешь подсчитать, сколько капель дождя ещё останется в небе в каждую из следующих t t минут?

Учтите, что если в какой-то момент в туче остается меньше воды, чем из неё выливается каждую минуту, то в следующую минуту туча просто исчезнет.

Формат ввода

В качестве аргументов вашей функции передаются 4 параметра:

  • Целое число n n ( 1 ≤ n ≤ 1 0 5 ) (1 \le n \le 10^5) — количество туч.

  • Целое число t t ( 1 ≤ t ≤ 1 0 6 ) (1 \le t \le 10^6) — количество минут наблюдения.

  • Одномерные массивы a a и b b , где целые числа a i a_i и b i b_i обозначают объём воды в туче (в каплях) и скорость её опустошения ( 0 ≤ a i , b i ≤ 1 0 9 ) (0 \le a_i, b_i \le 10^9) .

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

Ваша функция должна вернуть массив длины t + 1 t + 1 .

  • r e s [ 0 ] res[0] — суммарное количество капель в небе до начала дождя.

  • r e s [ 1.. t ] res[1..t] — количество капель, оставшихся в небе после каждой из t t минут.

Примечание

Во входных данных идут пары чисел a i a_i и b i b_i , обозначающие объём воды в туче (в каплях) и скорость её опустошения ( 0 ≤ a i , b i ≤ 1 0 9 ) (0 \le a_i, b_i \le 10^9) .

Ограничения

Ограничение времени
2 с
Ограничение памяти
256 МБ

Примеры

Пример 1

Ввод
6 6
12 2
10 3
3 1
5 4
7 2
9 1
Вывод
46
33
23
14
9
6
3

Теги

3.7.2
Нужно войти, чтобы отправить решение.Войти