Сканирующая прямая

Организаторы детского праздника планируют надуть для него M воздушных шариков. С этой целью они пригласили N добровольных помощников, i-й среди которых надувает шарик за Ti минут, однако каждый раз после надувания Zi шариков устает и отдыхает Yi минут. Теперь организаторы праздника хотят узнать, через какое время будут надуты все шарики при наиболее оптимальной работе помощников, и сколько шариков надует каждый из них. (Если помощник надул шарик, и должен отдохнуть, но больше шариков ему надувать не придется, то считается, что он закончил работу сразу после окончания надувания последнего шарика, а не после отдыха).

Входные данные
В первой строке входных данных задаются числа M и N (0 <= M <= 15000, 1 <= N <= 1000). Следующие N строк содержат по три целых числа - T_i, Z_i и Y_i  соответственно (1 <= T_i, Y_i <= 100, 1 <= Z_i <= 1000).

Выходные данные
Выведите в первой строке число T - время, за которое будут надуты все шарики. Во второй строке выведите N чисел - количество шариков, надутых каждым из приглашенных помощников. Разделяйте числа пробелами. Если распределений шариков несколько, выведите любое из них.

Углубившись на карантине в изучение физики, коровы открыли "му-частицы"
В настоящий момент они проводят эксперимент с N "му-частицами" (1 ≤N ≤ 10⁵). Частица i имеет "спин", описываемый двумя целыми числами x_i и y_i в диапазоне −10⁹…10⁹ включительно. Иногда две "му-частицы" взаимодействуют. Это может случиться только с такими частицами со спинами (x_i,y_i) и (x_j,y_j) у которых x_i≤x_j и y_i≤y_j. При этих условиях ровно одна из этих частиц исчезает (а с другой ничего не случится). В каждый момент времени может случиться не более одного взаимодействия.

Коровы хотят узнать минимальное количество "му-частиц", которые могут остаться после некоторой произвольной последовательности взаимодействий.

Входные данные
Первая строка содержит одно целое число N, начальное число "му-частиц". Каждая из последующих N строк содержит два разделённых пробелом целых числа, определяющих спин этой частицы. Все спины различны.
Выходные данные
Одно целое число, минимальное количество "му-частиц", которые могут остаться после некоторой произвольной последовательности взаимодействий.

Примеры

№	Входные данные	Выходные данные	Примечание
1	4 1 0 0 1 -1 0 0 -1	1	Одна из возможных последовательностей взаимодействий: Частицы 1 и 4 взаимодействуют, частица 1 исчезает. Частицы 2 и 4 взаимодействуют, частица 4 исчезает. Частицы 2 и 3 взаимодействуют, частица 3 исчезает. Только частица 2 остаётся.
2	3 0 0 1 1 -1 3	2	Частица 3 не может взаимодействовать ни с одной из других частиц, поэтому она должна остаться. Одна из частиц 1 и 2 тоже должна остаться.

Новый Президент Тридевятой республики начал свою деятельность с полной ревизии системы общественного транспорта страны. В результате на основе социологических опросов населения было составлено идеальное ежедневное расписание движения междугородних автобусов, утвержденное Парламентом республики.

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

Автобусная сеть страны охватывает N городов, занумерованных целыми числами от 1 до N.

Идеальное расписание содержит M ежедневных рейсов, i-й рейс начинается в городе F_i в момент времени X_i и заканчивается в некотором другом городе G_i в момент времени Y_i. Продолжительность каждого рейса ненулевая и строго меньше 24 часов. Рейс i выполняется одним из автобусов, находящихся в момент времени X_i в городе Fi.

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

Предполагается, что расписание будет действовать неограниченное время, поэтому может оказаться так, что его невозможно обслужить никаким конечным числом автобусов.

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

Входные данные
В первой строке задаются целые числа N и М (1 ≤ N, M ≤ 100 000) — количество городов и рейсов автобусов соответственно.

В каждой из следующих M строк содержится описание рейса автобуса: номер города отправления F_i, время отправления X_i, номер города назначения G_i (Fi ≠ Gi), время прибытия Y_i, отделенные друг от друга одним пробелом. Время прибытия и отправления задается в формате HH:MM, где HH — часы от 00 до 23, MM — минуты от 00 до 59.

Выходные данные
Выведите одно число — минимально необходимое количество автобусов. Если расписание невозможно обслуживать в течение неограниченного периода времени конечным числом автобусов, выведите число -1.

Примеры

№	Входные данные	Выходные данные
1	4 6 1 10:00 2 12:00 1 10:00 3 09:00 3 12:00 4 23:00 2 11:00 4 13:00 4 12:00 1 11:00 4 12:00 1 10:30	8

Том Сойер уговорил n своих друзей помочь ему в нелегком деле покраски забора, окружающего дом тетушки Полли. Забор представляет собой k последовательных досок, пронумерованных от 1 до k, причем после k-й доски опять идет первая.

Друзья Тома очень привередливы, i-й друг согласен участвовать в покраске только в том случае, если ему дадут покрасить участок из ровно ai последовательных досок. Кисточка у Тома только одна, поэтому друзья будут красить по очереди и сразу весь отведенный им отрезок. Тому остается лишь выбрать порядок, в котором приглашать друзей, а также выбрать для каждого желаемое количество последовательных досок.

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

Помогите Тому понять, сколько радости он сможет доставить своим друзьям.

Формат входных данных
Первая строка входного файла содержит два целых числа n (1 ≤ n ≤ 10⁵ ) и k (1 ≤ k ≤ 10⁹ ). Следующая строка содержит n целых чисел — значения a_i (1 ≤ a_i ≤ k).

Формат выходных данных
Выведите одно число — максимальное возможное значение x.
 

Ввод	Вывод
2 100 5 10	5
4 10 7 8 3 5	2

Пояснение
В первом примере x = 5, так как один из друзей просто не хочет красить больше пяти досок. Он придет первым, покрасит свои пять, после чего еще 10 неокрашенных досок достанется второму другу Тома. Оставшиеся 85 досок Тому придется красить самому.
Во втором примере достичь x = 2 можно, например, так. Сначала третий друг красит доски с 4 по 6 (3 неокрашенных доски). Затем четвертый друг красит доски с 1 по 5 (3 неокрашенных доски). Затем второй друг красит доски с 1 по 8 (2 неокрашенных доски). Наконец, первый друг красит доски с 6 по 10 и с 1 по 2 (2 неокрашенных доски, заметим, что забор идет по циклу и эти доски образуют последовательный отрезок).

Входные данные

Выходные данные

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

Примечание