Идёт 2163 год. Мишу, который работает в отделении таможни при космодроме города Нью-Питер, вызвал в кабинет шеф.
Как оказалось, недавно Министерство Налогов и Сборов выделило отделению определённую сумму денег на установку новых аппаратов для автоматического досмотра грузов. Естественно, средства были выделены с таким расчётом, чтобы грузы теперь находились на таможне ровно столько времени, сколько требуется непосредственно на их досмотр.
В руках шефа каким-то образом оказались сведения о надвигающейся ревизии – список из \(N\) грузов, которые будут контролироваться Министерством. Для каждого груза известны время его прибытия, отсчитываемое с некоторого момента, хранимого в большом секрете, и время, требуемое аппарату для обработки этого груза. Шеф дал Мише задание по этим данным определить, какое минимальное количество аппаратов необходимо заказать на заводе, чтобы все грузы Министерства начинали досматриваться сразу после прибытия. Необходимо учесть, что конструкция тех аппаратов, которые было решено установить, не позволяет обрабатывать два груза одновременно на одном аппарате. Напишите программу, которая поможет Мише справиться с его задачей.
На первой строке входного файла задано число \(N\) (0 ≤ \(N\) ≤ 50 000). На следующих \(N\) строках находится по 2 целых положительных числа \(T_i\) и \(L_i\) – время прибытия соответствующего груза и время, требуемое для его обработки (1 ≤ \(T_i\) ≤ \(10^6\), 1 ≤ \(L_i\) ≤ \(10^6\)).
В выходной файл выведите одно число – наименьшее количество аппаратов, которое нужно установить, чтобы не вызвать подозрений у Министерства.
3 3 2 4 2 5 2
2
5 13 4 15 1 11 5 12 3 10 3
3
В некоторой стране есть развитая сеть железных дорог. С доисторических времён и до нашего времени в стране непрерывно происходят военные перевороты, из-за которых в системе железнодорожного транспорта этой страны происходят непрерывные изменения. Дело в том, что во время очередного переворота некоторые дороги разрушаются из-за военных действий, а пока новый правитель некоторое время находится у власти, он восстанавливает часть дорог.
Временами железнодорожная система в этой стране становилась довольно разветвленной, поэтому некоторые города могли быть соединены двумя и более дорогами. Кроме того, дорога могла начинаться и заканчиваться в одном и том же городе, причем для одного города таких дорог могло быть несколько.
Инженер Джио проводит испытания новых сверхскоростных поездов. Поскольку поезда экспериментальные, у них не должно возникать трудностей при проезде через промежуточные города. Поэтому инженер Джио требует, чтобы ни в каком городе на пути поезда, кроме, может быть, начального и конечного, не было развилок. Точнее, из любого промежуточного города на пути поезда должны выходить либо ровно две дороги, ведущие в другие города (возможно, в один и тот же), либо ровно одна дорога, начинающаяся и заканчивающаяся в этом городе.
Естественно, что Джио желает испытать поезд на максимальной возможной скорости, и поэтому после каждого изменения в системе путей он хочет знать максимальную длину пути, по которому может ехать поезд. Поскольку в доисторические времена не умели добывать железо, в начале никаких дорог между городами нет.
В первой строке входного файла находятся целые положительные числа \(n\) (1 ≤ \(n\) ≤ 500) – число городов в стране, и \(m\) (1 ≤ \(m\) ≤ 50 000) – число изменений в железнодорожной системе. В следующих \(m\) строках находится информация об изменениях состояния системы путей. Каждое изменение является либо добавлением дороги, либо удалением дороги. В случае добавления дороги в очередной строке записан ноль, а затем идут три целых числа. Первые два из них являются номерами городов, соединяемых дорогой, а последнее является длиной добавленной дороги. Города нумеруются целыми числам от 1 до \(n\). Длина дороги является целым положительным числом, не превосходящим \(10^6\). В случае удаления дороги в очередной строке сначала записана единица, а затем идёт номер шага, на котором произошло добавление удаляемой дороги. Шаги нумеруются целыми числами, начиная с 1.
Для каждого изменения системы путей выведите в очередную строку выходного файла символ `*', если после очередного изменения системы путей существует сколь угодно длинный путь, удовлетворяющий условиям, поставленным Джио. В противном случае выведите в выходной файл единственное целое число, являющееся длиной максимального возможного пути.
7 10 0 7 6 7 0 6 5 6 0 5 4 5 0 4 3 4 0 3 2 3 0 2 1 2 1 1 1 2 1 3 1 4
7 13 18 22 25 27 20 14 9 5
Игорь работает младшим лаборантом в НИИ ихтиологии. Ему вверены \(n\) аквариумов, стоящих в ряд, в каждом из которых живет колония рыбок гуппи. Про каждую колонию заранее известна ее численность.
В лабораторных условиях НИИ ихтиологии колония рыбок гуппи растет по следующему правилу: достигнув популяции в \(f\) рыбок, колония живет в течении \(max(1000 - f, 1)\) секунд, после чего на свет появляется новая рыбка. От начального момента времени до рождения первой рыбки колония размера \(f\) также ждет \(max(1000 - f, 1)\) секунд.
Например, колония с начальным размером 996 будет размножаться следующим образом:
| момент времени | размер колонии | время до очередной рыбки |
|---|---|---|
| 0 | 996 | 4 |
| 4 | 997 | 3 |
| 7 | 998 | 2 |
| 9 | 999 | 1 |
| 10 | 1000 | 1 |
| 11 | 1001 | 1 |
| 12 | 1002 | 1 |
| ... | ... | ... |
Появление на свет каждой новой рыбки Игорь должен фиксировать в специальном журнале. Будем считать, что запись он делает мгновенно, но при этом он должен в момент рождения новой рыбки находиться рядом с аквариумом, в котором это произошло.
На перемещение от одного аквариума к соседнему у Игоря уходит одна секунда. В начальный момент времени Игорь стоит около первого аквариума.
Вычислите, в течение какого наибольшего периода времени Игорь сможет добросовестно выполнять свою работу.
В первой строке входного файла содержится целое число \(n\) (\(2 \le n \le 50\)) - количество аквариумов с рыбками гуппи в НИИ ихтиологии. Каждая из следующих \(n\) строк содержит одно целое число \(a_i\) (\(1 \le a_i \le 2007\)) - численность \(i\)-й колонии.
В выходной файл выведите момент времени, когда родится первая рыбка гуппи, запись о рождении которой Игорь сделать не сможет.
В приведенном примере Игорь сначала ждет у первого аквариума появления рыбки на 4-й секунде. После этого он бежит к третьему аквариуму (на это у него уходит 2 секунды) и как раз успевает к рождению рыбки на 6-й секунде. Однако вернуться к первому аквариуму, где следующая рыбка родится на 7-й секунде, он уже не успевает.
3 996 1 994
7