Задача A. Лифты ≡

Условие

N людей хотят попасть на L этаж. Сейчас они находятся на нулевом этаже. Они могут воспользоваться лифтами, коих E штук. Вместимость каждого лифта равна V. Каждый лифт может двигаться вверх и вниз со скоростью один этаж в секунду. Пешком по лестнице человек поднимается на один этаж за T секунд. Вместимость лестницы бесконечна. Какое минимальное количество времени должна потратить эта группа людей, чтобы всем оказаться на L этаже?

Формат входного файла

Входные данные содержат пять целых чисел: N, L, E, V, T.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 10⁹

1 ≤ L, E, V, T ≤ 10³

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

2 4 1 1 1

4

20 4 2 5 1000

12

Задача B. Карточный фокус ≡

Условие

Слон Пахом выучил карточный фокус и теперь показывает его всем. Суть фокуса в том, что слон должен отгадать карту, которую загадал игрок. Фокус выполняется следующим образом: берётся колода, состоящая из n карт, и совершается несколько итераций. На каждой итерации все карты раскладываются в m стопок по n/m карт в каждой. Пахом сам выбирает, как раскладывать карты. Далее игрок говорит, в какой стопке лежит карта, которую он загадал. Если слон Пахом уже может однозначно назвать карту, которую загадал игрок, то фокус заканчивается.

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

Формат входного файла

Первая строка входного файла содержит целые числа n, m.

Формат выходного файла

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

Ограничения

2 ≤ n, m ≤ 10⁹

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

4 2

2

30 5

3

10 10

1

Задача C. Контроль за выловом рыбы ≡

Условие

Всего для вылова доступно P видов рыб. Известно, что компания владелец рыболовного судна получила квоты на вылов w_i килограмм i-го вида рыбы.

Рыболовное судно выловило N рыб, i-я рыба имеет вес m_i. Каждая из выловленных рыб отнесена к одному из P видов.

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

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

Формат входного файла

Первая строка входного файла содержит целые числа P, N, K. Во второй строке содержится P целых чисел w_i — размер квоты в килограммах на вылов рыбы вида i. В третьей строке содержится N пар целых чисел m_i и t_i — масса и вид, к которому отнесли рыбу с номером i рыболовы.

Формат выходного файла

Выходной файл должен содержать строку "NO", если рыболовы точно не нарушили ограничения по квотам. В противном случае "YES".

Ограничения

1 ≤ N, P ≤ 10⁵, 0 ≤ K ≤ 10⁵, 1 ≤ w_i, m_i ≤ 10⁹, 1 ≤ t_i ≤ P

Описание подзадач и системы оценивания

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

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

2 5 2
5 6
1 1 1 1 1 1 1 2 1 2

NO

2 2 1
3 6
3 1 6 2

YES