Падают яблоки!
В определённые моменты времени некоторое количество яблок падает в некоторые точки
числовой прямой. В определённый момент времени некоторые коровы появляются на числовой
прямой и НАЧИНАЮТ ловить яблоки.
Если яблоко падает на числовую прямую и корова его не поймала, оно исчезает бесследно.
Если корова и яблоко прибыли в одно и то же время, корова ловит яблоко. Каждая корова может
перемещаться на одну единицу за секунду. Если корова поймала яблоко, она покидает
числовую прямую.
Сколько максимально яблок смогут поймать коровы, если будут действовать сообща оптимально?
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\) (
\(1\le N\le 2\cdot 10^5\)), количество раз когда яблоки
падали на числовую прямую или там появлялись коровы.
Каждая из последующих \(N\) строк содержит четыре целых числа \(q_i\), \(t_i\), \(x_i\), \(n_i\)
(\(q_i\in \{1,2\}, 0\le t_i\le 10^9, 0\le x_i\le 10^9, 1\le n_i\le 10^3\)).
- Если \(q_i=1\), это значит, что \(n_i\) коров прибыли на числовую прямую в момент времени \(t_i\)
в позицию \(x_i\).
- Если \(q_i=2\), это значит, что \(n_i\) яблок упали на числовую прямую в момент времени \(t_i\)
в позицию \(x_i\).
Гарантируется, что все упорядоченные пары \((t_i,x_i)\) различны.
ФОРМАТ ВЫВОДА (на экран / stdout):
Максимальное количество яблок, которое коровы могут поймать сообща.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 5 10 100
2 6 0 3
2 8 10 7
1 2 4 5
1 4 7 6
|
10
|