Очень легкая задача - 2

Сегодня утром жюри решило добавить в вариант олимпиады еще одну, Очень Легкую Задачу. Ответственный секретарь Оргкомитета напечатал ее условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать еще N копий. В его распоряжении имеются M ксероксов, каждый из которых копирует лист за х секунд. (Разрешается использовать все ксероксы одновременно. Можно копировать не только с оригинала, но и с копии.) Помогите ему выяснить, какое минимальное время для этого потребуется.

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


Формат входных данных
В первой строке записаны да натуральных числа N, M  разделенные пробелом (1 ≤ N, M ≤ 2•10⁸), во второй строке записаны скорости всех ксероксов - x (1 ≤ x ≤ 10 )


Формат выходных данных
Выведите одно число – минимальное время в секундах, необходимое для получения N копий.
 

Интересные числа

Квадратный корень и квадратный квадрат

Примеры

Очень легкая задача

Сегодня утром жюри решило добавить в вариант олимпиады еще одну, Очень Легкую Задачу. Ответственный секретарь Оргкомитета напечатал ее условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать еще N копий. В его распоряжении имеются два ксерокса, один из которых копирует лист за х секунд, а другой – за y.
Разрешается использовать как один ксерокс, так и оба одновременно. Можно копировать не только с оригинала, но и с копии. Помогите ему выяснить, какое минимальное время для этого потребуется.

Входные данные: на входе задается три натуральных числа N, x и y, разделенные пробелом (\(1 <= N <= 2 \cdot 10^8,\ 1 <= x, y <= 10\)).

Выходные данные: выведите одно число – минимальное время в секундах, необходимое для получения N копий.
 

Примеры

Вырубка леса

Фермер Николай нанял двух лесорубов: Дмитрия и Федора, чтобы вырубить лес, на месте которого должно быть кукурузное поле. В лесу растут X деревьев.

Дмитрий срубает по A деревьев в день, но каждый K-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в K-й, 2K-й, 3K-й день, и т.д.

Федор срубает по B деревьев в день, но каждый M-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в M-й, 2M-й, 3M-й день, и т.д.

Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают A + B деревьев, в дни, когда отдыхает только Федор — A деревьев, а в дни, когда отдыхает только Дмитрий — B деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.

Фермер Николай хочет понять, за сколько дней лесорубы срубят все деревья, и он сможет засеять кукурузное поле. Требуется написать программу, которая по заданным целым числам A, K, B, M и X определяет, за сколько дней все деревья в лесу будут вырублены.

Входные данные: на вход подаётся пять целых чисел, разделенных пробелами: A, K, B, M и X (\(1 <= A,\ B <= 10^9\) , \(2 <= K,\ M <= 10^{18}\), \(1 <= X <= 10^{18}\)).

Входные данные: выведите одно целое число — искомое количество дней.
 

Примеры

*Рапорт

Acowdemia

Беси опубликовала N статей (1 <= N <= 10⁵). i-ая статья процитирована ci раз (0 <= c_i <= 10⁵).
h-индекс это наибольшее число h такое, что имеется не менее h статей, каждая из которых цитируется не менее чем h раз. Например, есть 4 статьи с количествами цитат (1,100,2,3), тогда h-индекс равен 2, а при количествах цитат (1,100,3,3) h-индекс равен 3.

Чтобы повысить свой h-индекс, Беси планирует написать K обзорных статей (0 <= K <= 10⁵), каждая из которых цитирует несколько ее прошлых статей. Беси имеет право цитировать не более L статей в каждом обзоре (0 <= L <= 10⁵). Конечно, никакая статья не может цитироваться более одного раза в одном обзоре (однако статья может цитироваться в нескольких обзорах).

Помогите Беси определить максимальный h-индекс, который она может достичь после написания этих обзорных статей. Беси не может цитировать обзор в любом из её обзоров.

Входные данные
Первая строка содержит N, K, L. Вторая строка содержит N разделённых пробелом целых чисел c1,...,cN.

Выходные данные
Максимальный h-индекс.
 

Примеры

То березка, то рябина…

В целях улучшения ландшафтной архитектуры и экологической обстановки управление городского хозяйства разработало проект программы озеленения центрального проспекта. Согласно проекту, с одной стороны проспекта планируется высадить в ряд деревья K различных видов, для чего были закуплены саженцы деревьев, причем i-го вида было закуплено a_i саженцев.

Для достижения эстетического совершенства высаживаемого ряда деревьев требуется, чтобы среди любых P подряд идущих деревьев все деревья были разных видов. Если количество деревьев в ряду меньше P, то все они должны быть различны.

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

Входные данные
В первой строке вводятся два целых числа: K — количество различных видов деревьев (1 ≤ K ≤ 100 000), и P — требуемое количество подряд идущих деревьев разных видов (2 ≤ P ≤ K). Последующие K строк  входных данных содержат целые числа ai, задающие количество закупленных саженцев деревьев i-го вида  (1 ≤ a_i ≤ 10⁹), по одному числу в каждой строке.

Выходные данные
Выведите единственное число — максимальное количество деревьев, посадка которых в ряд в некотором порядке достигает эстетического совершенства.

 

Примеры

Социальное дистанцирование

Болеющие коровы решили помочь Фермеру Джону.
Для того, чтобы ограничить передачу болезни, N (2 ≤ N ≤ 10⁵) коров ФД решили попрактиковаться в "социальном дистанцировании" и "распределились" по ферме. Ферма представлена в виде прямой линии, с M взаимно не имеющими общих точек интервалами (1 ≤ M ≤ 10⁵), на которых растёт трава. Коровы хотят расставиться в точках с различными координатами, каждая точка покрыта травой, так, чтобы максимизировать значение D. Где D представляет расстояние между ближайшей парой коров. Помогите коровам определить наибольшее значение D.

Входные данные
Первая строка ввода содержит N и M. Каждая из следующих M строк описывает интервал двумя целыми числами a и b, где 0 ≤ a ≤ b ≤10¹⁸. Никакие два интервала не перекрываются и не касаются своими конечными точками. Корова, стоящая на конечной точке интервала считается стоящей на траве.
Выходные данные
Выведите наибольшее возможное значение D такое, что все пары коров не менее чем на D единиц друг от друга. Гарантируется, что существует решение с D>0.

Примеры

Подстрока

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

Входные данные
В первой строке даны два целых числа n и k (1 ≤ n ≤ 100000, 1 ≤ k ≤ n ) , где n – количество символов в строке. Во второй строке n символов – данная строка, состоящая только из строчных латинских букв.

Выходные данные
В выходной файл выведите два числа – длину искомой подстроки и номер её первого символа. Если решений несколько, выведите любое.

Примеры

Автомобиль "Пантера"

Однажды утром Глеб с ужасом осознал, что проспал, а пары в «Высшем университете» начинаются уже скоро. Опоздать было бы не так страшно, если бы он их и не вёл. К счастью, автомобиль Глеба «Пантера» довольно мощный: для упрощения будем считать, что за одну секунду он может сначала или увеличить скорость на 1, или уменьшить скорость на 1, или не менять её, а после этого его автомобиль проезжает x метров, где x - его текущая скорость в метрах в секунду. Потом он снова принимает решение об изменении скорости. Начальная скорость автомобиля преподавателя в момент, когда он только выезжает из дома, равна нулю. Путь до университета от его дома не близкий: нужно проехать d метров.

Глеб, обеспокоенный за знания своих студентов, хочет попасть в университет как можно раньше, чтобы успеть подготовиться к проведению лекции. К сожалению, на проезде на парковку университета установлен шлагбаум, поэтому скорость автомобиля после того, как он проехал ровно d метров должна быть равна 0.

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

Вводится одно целое число - d (1 <= d <= 10¹⁸), расстояние до университета.

Обратите внимание, что входные данные могут быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.

В первом тесте из условия Глебу выгодно действовать следующим образом:

1. Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
2. Не менять скорость, проехать один метр; скорость 1 м/с, проехал 2 метра от дома.

3. Уменьшить скорость на один; скорость 0 м/с, проехал 2 метра от дома.

Таким образом, он потратит 3 секунды, и его конечная скорость будет равно 0 м/с.

Во втором тесте из условия Глебу выгодно действовать, например, так:

1. Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
2. Увеличить скорость на один, проехать два метра; скорость 2 м/с, проехал 3 метра.
3. Увеличить скорость на один, проехать три метра; скорость 3 м/с, проехал 6 метров.
4. Уменьшить скорость на один, проехать два метра; скорость 2 м/с, проехал 8 метров.
5. Уменьшить скорость на один, проехать один метр; скорость 1 м/с, проехал 9 метров.
6. Не менять скорость, проехать один метр; скорость 1 м/с, проехал 10 метров.
7. Уменьшить скорость на один; скорость 0 м/с, проехал 10 метров.

    

Таким образом, он потратит 7 секунд, и его конечная скорость будет равно 0 м/с.

Примеры

2

3

10

7

Бесконечная Дженга

Летовец и его друг Московец придумали правила игры в бесконечную Дженгу.
В бесконченой Дженге каждый ход заключается в одном из двух действий на выбор игрока:

• если в башне есть хотя бы один брусок, то можно вытащить и убрать из башни ровно один брусок (количество брусков в башне уменьшается на 1);
• поставить на башню количество брусков на 1 больше, чем ставили в последний раз перед этим.

Например, можно выполнить такую последовательность действий при игре:

После 9 ходов, количество брусокв в башне в итоге будет равно 11, а по ходу игры из башни извлекли 4 бруска.

Известно, что Летовец и Московец сделали n ходов в придуманной игре, при этом после всех выполненных ходов, количество брусков в башне равнялось k. Найдите суммарное количество убранных друзьями с башни брусков за все n ходов. Гарантируется, что для заданных n и k ответ существует.

В первой строке входных данных заданы два целых числа n и k (1<=n<=10⁹; 0<=k<=10⁹) - суммарное количество ходов и количество брусков в башне после n ходов. Гарантируется, что для заданных n и k ответ существует.

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

Примеры

1 1

0

9 11

4

5 0

3

3 2

1

Эстафета

На сборы по программированию пригласили N учащихся. Вечерний досуг было решено провести в виде эстафеты. Для проведения эстафеты необходимо разбить всех учащихся на R команд по С человек в каждой. По мнению руководителя сборов, команда будет тем успешнее на эстафете, чем менее будет различаться рост учащихся в одной команде. 
Числом неуспешности команды будем называть разность между ростом самого высокого и ростом самого низкого членов этой команды (если в команде только один человек, то эта разница равна 0).
Вожатые решили сформировать команды так, чтобы максимальное из чисел неуспешности сформированных команд было минимально. Пока вожатые заняты расселением учащихся по домикам, помогите им и вычислите наименьше возможное значение максимального числа неуспешности сформированных команд.

Рассмотрим следующий пример. Пусть на сборах 8 человек, рост которых в сантиметрах равен 170, 205, 225, 190, 260, 130, 225, 160, и необходимо сформировать две команды по три человека в каждой. Тогда одним из вариантов является такой:
1 команда: учащиеся с ростом 225, 205, 225
2 команда: учащиеся с ростом 160, 190, 170
При этом число неуспешности первой команды будет равно 20, а число неуспешности второй — 30. Максимальное из чисел неуспешности будет 30, и это будет наилучший возможный результат.

Входные данные
Первая строка входных данных содержит три натуральных числа N, R и C - количество учащихся на сборах, количество команд и количество человек в каждой команды (1 <= R·C <= N <= 100 000). 
Далее вводятся N целых чисел — рост каждого из N учеников. Рост ученика - натуральное число, не превышающее 1 000 000 000.

Выходные данные
Выведите одно число - наименьше возможное значение максимального числа неуспешности сформированных команд.

 

Примеры

8 2 3
170
205
225
190
260
130
225
160

30

MEX(A)

Определим функцию mex следующим образом: mex(A) — это минимальное положительное целое число, которое отсутствует в множестве A. 

Например, mex множества {1, 2, 3, 5, 100}  равен 4, а mex множества {2, 3, 4, 5}  равен 1.

У вас есть множество чисел A, состоящее из n целых положительных чисел, и положительное число k. Затем вы k раз произвели следующую операцию: добавили в множество A ещё одно число, равное mex(A), тем самым, каждый раз увеличивая размер множества A на один.

По заданному множеству A и числу k определите последнее число, которое было добавлено в множество.

Входные данные
В первой строке заданы два целых числа n и k (1<=n<=100000, 1<=k<=10⁹) — количество чисел в множестве и количество операций добавления числа.
Вторая строка содержит n различных целых чисел a1, a2, ..., an (1<=a_i<=100000) — элементы множества A.

Выходные данные
Выведите одно целое число — последнее число, которое было добавлено в множество.

Примечание
В первом примере mex множества {1, 2, 4, 5}  равен 3, после добавления mex в множество, оно станет равным {1, 2, 3, 4, 5}.

 

Примеры

4 1
4 2 1 5

3

7 10
1 3 20 2 7 45 5

15

Agar.io

В многопользовательской игре Agar.io игроки управляют бактериями. У каждой бактерии есть размер — целое положительное число. Если встречаются две бактерии разного размера, то бактерия большего размера поглощает меньшую бактерию. При этом меньшая бактерия исчезает, а размер большей бактерии увеличивается на размер меньшей бактерии. Если встречаются две бактерии равного размера, то ничего не происходит. Побеждает игрок, чья бактерия останется на игровом
поле одна.
В игре участвуют n игроков, вам даны размеры их бактерий. Определите, какие из игроков имеют возможность выиграть в этой игре.

Формат входных данных
Программа получает на вход целое число n, 1 ≤ n ≤ 10⁵ — количество игроков. Следующие n строк содержат по одному числу a_i — размеры бактерий, 1 ≤ a_i ≤ 10⁹. Числа a_i заданы в порядке неубывания.
Формат выходных данных
Программа должна вывести n чисел равных «0» или «1», по одному числу в строке. Если i-е число равно 0, то это означает, что i-й игрок (размер бактерии которого первоначально был равен
a_i) ни при каких обстоятельствах не может выиграть в этой игре. Если i-е число равно 1, то это означает, что i-й игрок имеет возможность выиграть в этой игре.

Примеры

Распределение продуктов

В Сильвертауне расположены n розничных магазинов. В логистический центр города доставили m типов товаров с различным количеством, которые необходимо распределить по всем розничным магазинам. Логистическому центру необходимо распределить все товары по магазинам, следуя следующим правилам:

- Каждому магазину распределяется не более одного типа товара, но любое его количество.
- После распределения каждому магазину предоставляется некоторое количество товаров (возможно нулевое).

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

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

Примеры

Дремучий лес

Василий собирает ягоды

Медведь Василий собирает ягоды. Он будет счастлив, если ягод малины в его корзинке окажется не менее трети от общего числа ягод. Медведь Василий уже собрал N ягод, из них K штук малины. Василий уже изрядно устал собирать ягоды, поэтому помогите ему понять, какое минимальное число ягод малины ему необходимо собрать, чтобы быть счастливым. 


Входные данные
Программа получает на вход два целых числа N и K (N > 0, 0 ≤ K ≤ N, K<=10⁹, N<=2*10⁹), записанные в отдельных строках, — текущее количество ягод в корзинке медведя Василия и количество ягод малины в корзинке.

Выходные данные
Выведите единственное число — минимальное число ягод малины, которое необходимо собрать.

 

Примеры

Василий собирает ягоды

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

Формат входных данных
Программа получает на вход два целых числа N и K (N > 0, 0 ≤ K ≤ N, K<=10⁹, N<=2*10⁹), записанные в отдельных строках, — текущее количество предметов и количество любимых предметов, которые Летовец уже выбрал.

Формат выходных данных
Выведите единственное число — минимальное число любимых предметов, которые необходимо выбрать.

Примечение
В примере всего предметов 27, из которых любимых 7.
Если в выбрать ещё 3 любимых предмета, то всего станет 30 предметов, из которых любимых будет 10.
 

Бактерии

В биологической лаборатории проводят эксперимент. В начале у ученых есть \(n\) замороженных бактерий, пронумерованных от \(1\) до \(n\).

Согласно плану эксперимента замороженная бактерия с номером \(i\) попадёт в чашку Петри через \(a_i\) секунд после начала эксперимента. Если таких бактерий несколько, они все попадают туда одновременно.

Как только замороженная бактерия оказывается в чашке Петри, она размораживается и начинает созревать. Созревание бактерии с номером \(i\) занимает \(t_i\) секунд. Как только бактерия созрела, она начинает размножаться: немедлено превращается в две созревшие бактерии, и затем каждая созревшая бактерия в конце каждой секунды снова делится на две созревшие бактерии.

Размером колонии называется общее количество бактерий в чашке Петри. Цель эксперимента — определить, через сколько секунд размер колонии будет в точности равен \(m\).

Помогите ученым определить искомое число секунд или выясните, что размер колонии никогда не будет в точности равен \(m\).

Формат входных данных
В первой строке даны целые числа \(n\), \(m\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le m \le 10^{9}\)) — количество замороженных бактерий и желаемый размер колонии.

Во второй строке даны \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^{9}\)) — времена перемещения замороженных бактерий в чашку Петри.

В третьей строке даны \(n\) целых чисел \(t_1, t_2, \ldots, t_n\) (\(1 \le t_i \le 10^{9}\)) — продолжительность созревания замороженных бактерий.

Формат выходных данных
Если размер колонии никогда не будет равен \(m\), выведите \(-1\).

В противном случае выведите число секунд после начала эксперимента, через которое размер колонии будет в точности равен \(m\).

Рассмотрим, как развивается эксперимент в первом примере.

Бинарный (двоичный) поиск по ответу (C++)

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

Вы уже выпустили n версий [1, 2, ..., n] и забыли проверить на качество все, кроме последней. Теперь, вы хотите найти первую плохую версию, которая приводит к тому, что все последующие становятся плохими. 

Руководитель отдела качества очень хорошо к вам относится и написал для вас функцию isBadVersion(version), которая определяет является ли версия резила плохой (возвращает True, если версия плохая, и False если хорошая).

Теперь вам необходимо реализовать функцию для поиска первой плохой версии. Вы должны как можно быстрее определить с какой версии пошел плохой релиз, поэтому количество использования функции isBadVersion(version) должно быть минимальным.
Ваша функция должна вернуть номер первого плохого релиза.

Тайлер украшает площадь

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

Формат входных данных
В первой строке вводится натуральное число n (1 ≤ n ≤ 2·105)- количество коробок, выданных Тайлеру. Во второй строке записаны n чисел ai (1 ≤ ai ≤ 109)- количество плиток в i-й коробке.

Формат выходных данных
Выведите YES, если Тайлер сможет из всех плиток замостить квадрат какого-либо размера на площади, в противном случае выведите NO.

Чет-нечет

Автобусы

В столице одной Очень Демократической Страны все жители в 8 часов утра одновременно выходят со станций метро, ближайших к месту своей работы, и дальше добираются до работы на автобусах. Мэр города хочет построить еще одну станцию метро так, чтобы после этого время, к которому все люди доберутся до места своей работы (то есть время, когда последний работник окажется на работе), было наименьшим возможным.

Автобусное сообщение в столице устроено следующим образом. Есть N автобусных остановок, в частности, возле каждой станции метро расположено по остановке. Между N – 1 парой остановок постоянно курсируют автобусы, время движения от одной остановки до другой – 1 минута. Временем ожидания и пересадки можно пренебречь. Автобусное сообщение в столице организовано так, что от любой автобусной остановки до любой другой можно добраться на автобусах (возможно, с пересадками).

Входные данные
В первой строке входных данных содержатся два числа N и M – количество автобусных остановок и станций метро соответственно (2 ≤ N ≤ 50 000, 1 ≤ M ≤ 1 000, M < N).

Во второй строке задаются через пробел M чисел – номера автобусных остановок, рядом с которыми есть станции метро (каждая – не более одного раза).

В следующих N – 1 строках записано по два числа – номера автобусных остановок, между которыми курсирует автобус. (Автобус ходит в обоих направлениях. Каждый маршрут указан один раз.)

Выходные данные
Выведите два числа – сначала наибольшее время за которое кто-то будет и после строительства добираться на работу, а затем номер автобусной остановки, рядом с которой следует построить новую станцию метро. (Строить можно возле тех автобусных остановок, возле которых еще нет станций метро). Если решений несколько, выведите одно из них.
 

Сад

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

Байтмен хочет установить забор, огораживающий прямоугольные области. Для экономии денег забор должен быть как можно короче. Ваша задача – помочь Байтмену выбрать две прямоугольные области.

Сад представляет собой прямоугольник длиной l метров и шириной w метров, который разделен на l·w одинаковых единичных квадратов размером 1x1 метр каждый. Зафиксируем координатную систему так, чтобы оси координат были параллельны сторонам сада. Все квадраты имеют целые координаты (x,y), удовлетворяющие ограничениям 1 <= x <= l, 1 <= y <= w. В каждом единичном квадрате может содержаться любое количество роз.

Стороны прямоугольных областей, которые выбираются, должны быть параллельны сторонам сада, а их угловые единичные квадраты – иметь целые координаты. Прямоугольная область с угловыми единичными квадратами (l₁,w₁), (l₁ ,w₂), (l₂, w₁) и (l₂,w₂) (для 1 <= l₁ <= l₂ <= l и 1 <= w₁ <= w₂ <= w):

• содержит все единичные квадраты с координатами (x,y), которые удовлетворяют условию l₁ <= x <= l₂ и w₁ <= y <= w2, и
• имеет периметр 2 · (l₂−l₁+1)+ 2 · (w₂−w₁+1).

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

Задание
Напишите программу, которая:

• читает из стандартного ввода размеры сада, общее количество роз в саду, количество роз, которое должно находиться в каждой прямоугольной области, и позицию каждой розы в саду, определяемую координатами единичного квадрата, в котором она находится;
• находит угловые единичные квадраты двух таких прямоугольных областей с минимальной суммой периметров, которые удовлетворяют заданным условиям;
• выводит в стандартный вывод минимальное значение суммы периметров двух непересекающихся прямоугольных областей, каждая из которых содержит точно заданное количество роз (или единственное слово NO, если такой пары прямоугольных областей не существует).

Входные данные
Первая строка стандартного ввода содержит два числа: l и w (1 <= l, w <= 250), разделенных одним пробелом – длину и ширину сада. Во второй строке задаются два числа: n и k (2 <= n <= 5000, 1 <= k <= n/2), записанных через пробел и обозначающих общее количество роз в саду и количество роз, которое должно быть в каждой из прямоугольных областей. Следующие n строк содержат позиции роз, по одной розе в строке. Каждая (i+2)-я строка содержит два числа l_i, w_i (1 <= l_i <= l, 1 <= w_i <= w), разделенных одним пробелом – координаты квадрата, содержащего i-ю розу.

В одном квадрате может содержаться две или большее количество роз.

Выходные данные
В первую и единственную строку стандартного вывода ваша программа должна вывести одно число – минимальную сумму периметров двух неперекрывающихся прямоугольных областей, каждая из которых содержит ровно k роз, или единственное слово NO, если таких прямоугольников нет.

Рисунок к тесту:

Фонтан

Администрация одного института решила построить в холле фонтан. По плану администрации, фонтан должен иметь форму круга с максимально возможным радиусом. Дизайнеру сообщили, что холл института имеет вид прямоугольника, размером X×Y метров. Однако когда дизайнер стал выбирать место для фонтана, он столкнулся с серьезной проблемой: в холле института обнаружилось N круглых колонн, снести которые не представляется возможным.

Таким образом, у него появилась проблема: где следует поместить фонтан, чтобы он имел максимально возможный радиус и не имел ненулевого по площади пересечения с колоннами. Вам предстоит помочь ему в решении этой нелегкой задачи.

Входные данные
В первой строке входных данных содержатся вещественные числа X и Y, 1 <= X, Y <= 10⁴ . Будем считать, что прямоугольник холла расположен на координатной сетке так, что его углы имеют координаты (0, 0), (X, 0), (X, Y) и (0, Y).

Во второй строке задается число N (0 <= N <= 10) - количество колонн. Следующие N строк содержат параметры колонн - i-я строка содержит три вещественных числа X_i, Y_i и R_i - координаты центра и радиус i-й колонны (R_i <= X_i <= X-R_i, R_i <= Y_i <= Y-R_i, 0.1 <= R_i <= min(X / 2, Y / 2); для любых i ≠ j sqrt( (X_i - X_j)2 + (Y_i - Y_j)2 )>= R_i + Rj). Все вводимые числа разделены пробелами.

Выходные данные
Выведите три вещественных числа: X_F, Y_F и R_F - координаты центра и радиус фонтана. Фонтан должен быть полностью расположен внутри холла (допускается касание стен) и не иметь ненулевого пересечения ни с одной из колонн (допускается касание). Радиус фонтана должен быть максимален. Разделяйте числа пробелами и/или переводами строки. Если решений несколько, выведите любое из них.

Провода

Медиана объединений

Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

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

Входные данные
Сначала вводятся числа N и L (2≤N≤200, 1≤L≤50000). В следующих N строках задаются параметры, определяющие последовательности.

Каждая последовательность определяется пятью целочисленными параметрами: x₁, d₁, a, c, m. Элементы последовательности вычисляются по следующим формулам: x₁ нам задано, а для всех i от 2 до L: x₁ = x₁–1+d_i-1. Последовательность d_i определяется следующим образом: d₁ нам задано, а для i≥2 di=((a*d_i-1+c) mod m), где mod – операция получения остатка от деления (a*d_i-1+c) на m.

Для всех последовательностей выполнены следующие ограничения: 1≤m≤40000, 0≤a<m, 0≤c<m, 0≤d1<m. Гарантируется, что все члены всех последовательностей по модулю не превышают 10⁹.

Выходные данные
В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N-1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.

Электрик-ковбой Джо

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

Вот и сейчас ему поручили проверить два стоящих на расстоянии d друг от друга столба высоты h₁ и h₂ соответственно. Чтобы убедиться, что все хорошо, Джо должен побывать на вершинах обоих столбов.

Электрик-ковбой посещает столбы следующим образом: сначала он выбирает один из столбов и просто взбирается на него. Выполнив все работы на вершине, он спускается по этому столбу на некоторую высоту (возможно до самой земли), достает свое лассо и цепляется им за некоторую точку второго столба (это может быть произвольная точка). После этого Джо прыгает и двигается вниз по дуге окружности с центром в точке, за которую зацепилось лассо, пока не достигнет либо другого столба, либо земли.

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

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



Джо просит вас помочь ему выполнить работу, сообщив какое минимальное расстояние ему придется лезть вверх по столбам.

Входные данные
Входной файл содержит четыре положительных целых числа: d, h₁, h₂ и l - расстояние между столбами, высоту первого и второго столбов и максимальный допустимый перепад высот при прыжке, соответственно. Все числа во входном файле не превышают 10⁶.

Выходные данные
Выведите ответ с максимальной возможной точностью. Ответ будет проверяться с точностью до 10⁻⁵.

Японский кроссворд

Наиболее известная игра, дошедшая до нас из Японии – это Судоку. Новая игра должна затмить ее славу. Про нее известно следующее. Нам дан квадрат, разделенный сеткой на n×n клеток, а каждая клетка содержит картинку одного из k типов. Игрок должен переместить их, чтобы получить максимально возможное число одинаковых первых рядов (два ряда считаются одинаковыми, если оба заполнены одинаковыми картинками и в одинаковом порядке). По виду таблицы определите, сколько одинаковых рядов в ней можно сложить (если менять картинки как угодно).

Например, если нам дана такая таблица:

одно из результирующих состояний в игре будет:

Входные данные
Первая строка входных данных содержит два числа n (1≤n≤40000) и k (1≤k≤50000). Каждая из следующих k строк содержит число картинок в таблице каждого из k типов. Все числа больше 0, их сумма в точности равна n².

Выходные данные
Выведите в первой строке максимальное количество одинаковых рядов, которые можно построить из этих картинок. В следующих n строках выведите содержание таких рядов: в каждой строке должно находиться одно число – номер соответствующей картинке в порядке ее появления во входных данных. Если решений несколько, выведите любое из них.

Мастерство фотографии

Фотографа попросили сделать фотосессию группы детей для выпускного альбома в детском саду. В числе прочих, он должен сделать групповой снимок, на котором должны присутствовать все дети одновременно. Фотограф считает, что для красивой фотографии группы требуется очень тщательно расставить детей в кадре. В частности, с его точки зрения, группа должна расположиться как можно компактнее по ширине, то есть количество людей в самом длинном ряду на фотографии должно быть как можно меньше.
Для гармоничного расположения детей фотограф размещает детей не более чем в четыре ряда. Девочек он располагает либо во втором ряду, сидящими на стульчиках, либо стоящими в третьем ряду. Мальчиков он размещает либо в первом ряду, сидящими на корточках, либо в четвёртом ряду, стоящими на стульчиках. Группа состоит из a мальчиков и b девочек. В студии есть стулья в количестве c штук. Какие-то ряды могут быть пустыми. Все стулья использовать не обязательно.
По заданным числам a, b и c требуется определить, какого наименьшего по ширине расположения группы сможет добиться фотограф.
Формат входных данных
Программа получает на вход три целых неотрицательных числа a, b и c, записанных в отдельных строках — количество мальчиков, девочек и стульев соответственно. Все числа не превосходят 10¹⁸ .
Обратите внимание, что значения переменных в этой задаче могут превышать возможные значения 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Формат выходных данных
Вывести одно целое число — минимальную ширину группы, которую сможет организовать фотограф.

Замечание
Во всех примерах в условии группа состоит из 9 мальчиков и 15 девочек.
В первом примере стульев нет, поэтому все девочки стоят, все мальчики сидят на корточках, общая ширина группы 15.
Во втором примере есть 4 стула. Можно посадить 4 девочек во втором ряду на эти стулья, остальные 11 девочек будут стоять в третьем ряду. Все мальчики будут сидеть на корточках в первом ряду. Общая ширина группы 11.
В третьем примере есть 7 стульев. Тогда есть два способа получить группу ширины 9. Например, можно посадить на все стулья девочек, тогда в первом ряду будет 9 мальчиков, во втором ряду будет 7 девочек, в третьем ряду 8 девочек. Либо можно посадить на стулья 6 девочек и поставить одного мальчика в четвёртый ряд. Тогда получим 8 мальчиков в первом ряду, 6 девочек во втором, 9 девочек в третьем и 1 мальчика в четвёртом. В любом из этих двух случаев ширина группы равна 9.
В четвёртом примере стульев много и есть несколько способов организовать группу ширины 8. Один из способов такой: посадим на корточки 4 мальчика в первом ряду, далее посадим 8 девочек на стулья во втором ряду, оставшиеся 7 девочек встанут в третьем и 5 мальчиков поставим на стульчики в четвёртом.

6

В королевстве Полерам расположен длинный линейный сад из N деревьев, стоящих в один ряд (по порядку с запада на восток). У каждого дерева i (нумерация от 1 до N) имеется некоторый урожай a_i — количество собранных яблок (целое число, может быть положительным, нулевым или даже отрицательным, если учитывать затраты или потери).
Королевский интендант хочет упаковывать собранный урожай в большие ящики, рассчитанные ровно на K яблок. Для удобства он рассматривает непрерывные отрезки деревьев [L,R] и проверяет, делится ли сумма (a_L )+ (a_L+1) + … + (aR) на K без остатка. Если делится, то такой отрезок можно упаковать в ящики без недогруза и перегруза.
Требуется найти общее количество таких отрезков [L,R], для которых сумма урожая деревьев на этом участке кратно K, количество яблонь нечётное, а количество собранных яблок - положительное число.
Примечание:
В отрезке [L, R] должно быть выполнено неравенство 1<= L <= R <= N.
Формат входных данных
Первая строка: два целых числа N и K, (1 <= N <= 200000, 1 <= K <= 10⁶).
Вторая строка: N целых чисел a₁, a₂, …, a_N (-10⁶ <= a_i <= 10⁶).
Формат выходных данных
Выведите одно число — количество всех пар (L, R) для которых (a_L )+ (a_L+1) + … + (a_R) делится без остатка на K, количество яблонь нечётное, а количество собранных яблок - положительное число.

Пояснение: в данном примере есть четыре последовательности: (1 + 2), (1 + 2 + 3), (3), (6), в данном случае все с положительным количеством собранных яблок, но только 3 с нечётным количеством яблонь.

Building a Tall Barn

Фермер Джон строит новый \(N\)-этажный амбар с помощью своих \(K\) коров (\(1 \leq N \leq K \leq 10^{12}\) и \(N \leq 10^5\)). Чтобы сделать работу быстрее ему нужно оптимально распределить работу между коровами.

Каждая корова должна быть назначена на работу ровно на один этаж. И на каждый этаж должна быть назначена хотя бы одна корова. \(i\)-ый этаж требует выполнения \(a_i\) единиц работы , каждая корова завершает одну единицу работы ровно за час. Поэтому если \(c\) коров работают на этаже \(i\), то они выполнят всю работу ровно за \(a_i / c\) единиц времени. Из соображений безопасности, этаж \(i\) должен быть завершён прежде чем начнётся работа на этаже \(i+1\).

Вычислите минимальное количество времени, за которое может быть построен амбар, если коровы будут распределены по этажам оптимальным способом. Выведите это число округлённым к ближайшему целому. Гарантируется, что решение будет более чем на 0.1 от границы между двумя целыми числами.

Angry Cows

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

Имеется \(N\) стогов сена, расположенных в различных целочисленных позициях \(x_1, x_2, \ldots, x_N\) на числовой прямой. Если корова приземлится с энергией \(R\) в позиции \(x\), это вызовет взрыв "радиусом \(R\)", что вызовет взрывы всех стогов сена в диапазоне \(x-R \ldots x+R\). Все стоги сена в этом диапазоне также одновременно взрываются с радиусом взрыва \(R-1\). Все ещё не взорванные стоги сена, попавшие в этот диапазон, снова взрываются уже с радиусом взрыва \(R-2\), и т.д.

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

Wormhole Sort

Коровы Фермера Джона устали от ежедневных сортировок перед выходом из амбара. Они получили Ph.D по квантовой физике и готовы ускорить этот процесс.

Этим утром, как обычно \(N\) коров (\(1 \leq N \leq 10^5\)), последовательно пронумерованных \(1 \dots N\), находятся в амбаре на различных позициях, также пронумерованных \(1 \dots N\), так что корова \(i\) находится в позиции \(p_i\). Однако этим утром имеется \(M\) туннелей (\(1 \leq M \leq 10^5\)), которые пронумерованы \(1 \dots M\), при этом туннель \(i\) двунаправленно связывает позиции \(a_i\) и \(b_i\) и имеет ширину \(w_i\) ( \(1\le a_i,b_i\le N, a_i\neq bi, 1\le w_i\le 10^9\) ).

В любой момент времени две коровы, расположенные на противоположных концах туннеля могут параллельно поменяться позициями через него. Коровы могут таким образом меняться позициями сколько угодно раз пока корова \(i\) не окажется в позиции \(i\) для \(1 \leq i \leq N\).

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

Milking Order

\(N\) коров (\(1 \leq N \leq 10^5\)), фермера Джона, пронумерованных \(1 \ldots N\), разработали социальную иерархию, в соответствии с которой ФД доит их каждое утро.

ФД сделал \(M\) наблюдений об этой структуре (\(1 \leq M \leq 50,000\)). Каждое наблюдение - упорядоченный список некоторых из его коров, указывающий что их нужно доить именно в таком порядке. Например список 2 5 1 означает, он должен подоить корову 2, некоторое время спустя - корову 5 и некоторое время после - корову 1.

Наблюдения ФД приоритезированы, поэтому его цель - максимизировать значение \(X\) так, чтобы выполнились условия первых \(X\) наблюдений. Если несколько порядков дойки могут удовлетворять \(X\) наблюдениям, он выбирает тот, в котором корова с меньшим номером доится раньше. Иными словами, если несколько порядков дойки удовлетворяют этим условиям, ФД выбирает лексикографически наименьший. Порядок \(x\) является лексикографически меньшим, чем порядок \(y\), если для некоторого \(j\), , \(x_i = y_i\) для всех \(i < j\) и \(x_j < y_j\) (другими словами два порядка идентичны до некоторой точки, в которой \(x\) меньше чем \(y\)).

Помогите ФД определить наилучший порядок дойки его коров.

Sabotage

Фермер Пауль решил саботировать доильное оборудование Фермера Джона. Доильное оборудование составляет ряд из N (3 <= N <= 100,000) доильных машин, где i-ая машина производит M_i единиц молока. ФП планирует отсоединить непрерывный блок этих машин от i-ой до j-ой (2 <= i <= j <= N-1). Заметим, что ФД не собирается отключать первую и последнюю машины, поскольку это очень заметно и легко обнаружить. Цель ФП – минимизировать среднее производство молока оставшимися машинами.
Пожалуйста, помогите ФД определить минимальное среднее значение производства молока оставшимися машинами в случае оптимальных действий ФП.
PROBLEM NAME: sabotage
Формат входных данных
* Строки 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит M_i.
Формат выходных данных
* Строка 1: Минимально возможное среднее, которого может достичь ФП, округлённое до 3 цифр после десятичной точки и с выводом 3 цифр после десятичной точки.
Примечание
Оптимальное решение – удалить машины 7 т 8 оставив 5 1 2, среднее которых равно 8/3.

Tractor

Одно из полей Фермера Джона весьма холмисто. И он хочет купить новый трактор для работы на этом поле. Поле описывается решеткой из N x N (1 <= N <= 500) неотрицательных целых высот ячеек. Трактор может перемещаться из ячейки в соседнюю (на один шаг на север, юг, запад или восток), с разницей их высот D ровно за D единиц денег.
ФД хочет заплатить достаточно, так чтобы его трактор, начиная с некоторой ячейки поля мог посетить как минимум половину ячеек поля. Если число ячеек в поле - нечетное, то половина, округленная вверх.
Определите минимальную стоимость покупки трактора способного выполнить эту задачу.

PROBLEM NAME: tractor
Формат входных данных
* Строка 1: Значение N.
* Строки 2..1+N: Каждая строка содержит N разделенных одиночными пробелами неотрицательных целых чисел (каждое не более миллиона), определяющих строку поля ФД.
Формат выходных данных
* Line 1: Минимальная стоимость трактора, который способен объехать не менее половины этого поля.
Примечание
Трактор стоимостью 3 способен перемещаться из ячейки с высотой 0 в ячейку с высотой 3. Поэтому он может посетить все ячейки с высотами 0 и 3. Вместе они представляют не менее половины фермы.

Flowerpot

Фермер Джон нуждается в Вашей помощи в организации поливки. Вам даны координаты N поливателей (1 <= N <= 100,000) на декартовой плоскости, где y представляет высоту поливателя. А x - его местоположение на прямой.

Каждая капля воды падает вертикально (по направлению к оси x) со скоростью 1 единица в секунду. Вы должны разместить клумбу (шириной W) с цветами так, чтобы разница во времени, когда первая капля упадет на клумбу и когда последняя капля упадет на клумбу была не менее некоторой величины D. Капля, которая попадает на границу клумбы, считается попавшей на клумбу.
Вам даны значения D, а также местоположения и высоты поливателей. Вычислите минимально возможную величину W.
PROBLEM NAME: fpot
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа N и D. (1 <= D <=1,000,000) * Строки 2..1+N: Строка i+1 содержит разделенные пробелом координаты (x,y) поливателя i, все величины в интервале 0...1,000,000.
Формат выходных данных
* Строка 1: Одно целое число, минимально-возможную ширину клумбы. Выведите -1, если невозможно построить клумбу, которая получала бы воду в течение не менее D единиц времени
Примечание
Клумба шириной 2 возможна, если разместить ее с x от 4 до 6. Тогда она будет получать капли с поливателей #1 и #3, втечение времени 10-3 = 7.

Поезда

В связи с увеличившимся количеством аварий на железной дороге, руководство дороги решило изменить график движения поездов. Анализ состояния полотна дороги показал, что оптимальным является следующий график движения: сначала T₁ минуту поезд идет со скоростью V₁ метр в минуту, потом T₂ минуты со скоростью V₂ метра в минуту, ..., наконец, T_N минут со скоростью V_N метрв в минуту. При этом на любом из этих участков поезд может стоять (V_i = 0).

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

Входные данные
Первые две строки входных данных содержат числа L и N (100 ≤ L ≤ 10000, 1 ≤ N ≤ 1000). Далее идет N строк, задающих график движения поезда, каждая строка содержит пару чисел T_i и V_i (1 ≤ T_i ≤ 1000, 0 ≤ V_i ≤ 1000).

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

Поле для крикета

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

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

Задача слегка упрощена тем, что парк Короля имеет прямоугольную форму и расположен на плоской поверхности. Более того, границы парка параллельны направлениям север - юг и восток - запад. В то же время игра в королевский крикет всегда происходит на квадратном поле, границы которого также параллельны направлениям север - юг и восток - запад. Архитектор уже сопоставил парку прямоугольную декартову систему координат и точно определил координаты каждого дерева. Оси этой системы координат, конечно, параллельны направлениям север - юг и восток - запад. Юго-западный угол парка имеет координаты (0, 0), а северо-восточный - координаты (W, H), где W и H - длина и ширина парка соответственно.

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



Входные данные
Первая строка содержит три целых числа, N, W и H, разделённых пробелами: N - число деревьев в парке, W и H - длина и ширина парка соответственно.

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

Ограничения: 1 <= N <= 100, 1 <= W, H <= 10 000, 0 <= x_i <= W, 0 <= y_i <= H.

Выходные данные
Вывести через пробел три целых числа, P, Q и L, где (P, Q) - координаты юго-западного угла поля для крикета, L - длина его сторон. Если существует несколько возможных положений поля максимального размера, вывести любое.

Смешивание напитков

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

Напиток из таких сортов кофе можно описать следующим образом: всего в кружку налито \(n\) сортов, \(i\)-й сорт характеризуется уровнем крепости \(p_i\) и высотой слоя, который он занимает в кружке, \(h_i\). При этом если \(i < j\), то слой кофе \(i\)-го сорта находится ниже кофе \(j\)-го сорта. Также известно, что высота кружки равна \(\sum\limits_{i=1}^n h_i\), то есть верхний край самого верхнего слоя кофе находится ровно на уровне верхней границы кружки.

Для разнообразия иногда хочется получить из такого <<коктейля>> напиток определенного суммарного уровня крепости. Суммарный уровень крепости определяется как среднее взвешенное уровней налитых в кружку сортов, то есть как \[P = \frac{\sum\limits_{i=1}^n p_i \cdot h_i}{\sum\limits_{i=1}^n h_i} \text{.}\]

Чтобы как-то изменять \(P\), можно

1. выбрать трубочку произвольной высоты \(h\);

2. один или более раз выполнить следующее: погрузить ее в напиток на любую глубину от \(0\) до \(h\) включительно относительно верхнего края кружки (не относительно текущего уровня жидкости) и отпить произвольное (не обязательно целое) количество кофе с того уровня, на который попал нижний конец трубочки.

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

Ваша задача — ответить на запросы вида: можно ли из текущего напитка сделать напиток крепости \(t_i\), и если можно, то какая минимальная высота трубочки для этого понадобится. Поскольку идеально точную необходимую высоту трубочки вычислить может быть сложно, достаточно определить минимальное количество верхних слоев кофе, достаточное, чтобы, отпив какое-то количество кофе из некоторых из них, можно было добиться суммарной крепости напитка \(t_i\).

Формат входных данных
В первой строке ввода даны два целых числа \(n\) и \(q\) — количество слоев кофе в кружке и количество запросов (\(1 \le n, q \le 2 \cdot 10^5\)).

Следующие \(n\) строк содержат по два целых числа \(p_i\) и \(h_i\) — уровень крепости и высоту \(i\)-го снизу кружки слоя кофе (\(1 \le p_i, h_i \le 10^9\)). Гарантируется, что сумма \(p_i \cdot h_i\) по всем \(i\) не превосходит \(10^{18}\).

В \(i\)-й из следующих \(q\) строк дано единственное целое число \(t_i\), определяющее \(i\)-й запрос (\(1 \le t_i \le 10^9\)).

Формат выходных данных
Выведите \(q\) строк, в \(i\)-й из которых содержится единственное целое число от \(0\) до \(n\) — ответ \(i\)-й запрос. Если для какого-то запроса ответ такой, что нельзя добиться требуемого уровня крепости, выведите в качестве ответа на этот запрос число \(-1\).

Замечание
Для примера из условия:

1. В первом запросе, чтобы получить напиток крепости \(1\), достаточно выпить верхние два слоя кофе.

2. Во втором запросе достаточно выпить часть кофе со второго сверху слоя.

3. В третьем запросе понадобится выпить первый и третий слой кофе.

4. В четвертом запросе невозможно добиться уровня крепости \(4\).

Цветочный магазин

Петя открыл цветочный магазин. Магазин Пети занимается изготовлением и продажей букетов. Всего существует \(n\) видов цветов, занумерованных от 1 до \(n\). Каждый букет, чтобы быть гармоничным и красивым, должен состоять из цветов всех видов, по одной штуке каждого вида. В магазине уже есть \(a_i\) штук цветов вида \(i\). На цветочной базе можно купить цветок любого вида за 1 рубль.

Определите, сколько букетов сможет собрать Петя, если потратит не более \(x\) рублей на покупку цветов на базе. Ответьте на \(q\) запросов с различными \(x_i\).

Формат входных данных
В первой строке входных данных находятся два целых числа \(n\) и \(q\) (\(1 \le n, q \le 10^5\)) — количество различных типов цветов и количество запросов.

Во второй строке находятся \(n\) целых чисел \(a_1, a_2, \cdots, a_n\) (\(0 \le a_i \le 10^9\)) — количество цветов каждого вида, имеющихся в магазине.

В третьей строке находятся \(q\) целых чисел \(x_1, x_2, \cdots, x_q\) (\(0 \le x_i \le 10^9\)) — запросы Пети.

Формат выходных данных
Выходной файл должен содержать \(q\) чисел, где \(i\)-е число это максимальное количество букетов, которое можно собрать потратив не более \(x_i\) рублей.

Примечание
В первом примере у Пети изначально есть 1 цветок первого типа и 0 цветов второго типа.

В первом запросе у него есть 1 рубль, он покупает цветок второго типа и делает 1 букет.

Во втором запросе у него есть 2 рубля, он не может сделать два букета за 2 рубля, поэтому ответ по прежнему 1.

В третьем запросе у него есть 5 рублей, он покупает 2 цветка первого типа и 3 цветка второго типа и делает 3 букета.

Есть n стульев...

Ski Course Rating

Кубическое уравнение