Задача A. Жаркое лето ≡

Условие

Во Владивостоке выдалось очень жаркое лето. В день с номером i температура равна D * i. Для спасения от жары Саша может либо включать кондиционер, либо обкладываться льдом. Это сохранит температуру комфортной в течение всего дня.

Включить кондиционер стоит C рублей, а создание льда отнимет у Саши количество сил, равное температуре за окном. При этом, пока включен кондиционер, Саша восстанавливает K сил.

Найти количество дней, которые Саша сможет сохранять комфортную температуру, если в первый день у Саши было M рублей и E сил.

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

Входной файл содержит пять целых чисел M, E, C, D, K.

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

Выходной файл должен содержать одно число — количество дней, которые Саша сможет сохранять комфортную температуру.

Ограничения

1 ≤ M, E, C, D, K ≤ 10³;

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

10 10 2 3 5

8

100 80 10 8 14

15

Задача B. Наилучшее обучение ≡

Условие

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

Осталось всего два дня, в течение которых школьники будут решать контесты. Недавно в тестирующей системе появилось n новых задач, из которых и будут формироваться контесты. Причем сложность всех задач различна, и для первой задачи в списке равна a, а у каждой следующей на a больше, чем у предыдущей. Так как Игорь уже давал ребятам другие контесты, он знает, что суммарная сложность задач, которые школьники могут решить за день, равна b. При этом школьники не обязательно должны решить задачи суммарной сложностью ровно b. Помогите Игорю узнать максимальное количество задач, которое могут решить дети за два дня.

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

Первая строка входного файла содержит три целых числа a, n и b, разделенные пробелами.

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

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

Ограничения

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

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

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

5 10 15

3

10 10 10

1

Задача C. Вася и конструктор чисел ≡

Условие

У Васи есть любимый конструктор чисел. Он представляет из себя табличку длины N и неограниченный запас цифр от 0 до 9.

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

Пояснение к примерам.

Рассмотрим тест №3: даны 99999 - это "заевшие" цифры в изношенном конструкторе, получается, что крутость изношенного конструктора Для этого примера = 0, т.к. все цифры одинаковые. Для нового конструктора "шаблон" числа будет выглядеть как *****, куда, следуя логики Поиска максимальной суммы произведения, мы ставим 98989, получая 9*8 + 8*9 + 9*8 + 8*9 = 288. Ответ: 288 - 0 = 288

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

В первой строке записано число 1 ≤ N ≤ 10⁵. Во второй строке содержится S длины N, в которой на позиции i стоит  *  если позиция свободна, и на неё можно ставить любую цифру, в противном случае на i-й позиции записана цифра от 0 до 9.

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

Выведите единственное целое число: разницу между крутостью самого крутого числа в новом конструкторе и конструкторе Васи.

Ограничения

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

3
***

0

5
1*1*1

252

5
99999

288

Задача D. Чемпионат по боксу ≡

Условие

В чемпионате по боксу соревнуется две команды по N боксёров в каждой. Все боксёры разбиты на M весовых категорий. Каждый боксёр характеризуется уровнем мастерства p_i (при этом не существует двух боксёров с равным уровнем мастерства) и номером весовой категории в которой он выступает c_i. Чемпиона проходит по следующим правилам: все участники разбиваются по весовым категориям и в рамках одной весовой категории каждый боксёр одной команды выходит на ринг против каждого боксёра другой команды, за победу в бое начисляется одно очко. Боксёр точно победит если его уровень мастерства выше уровня мастерства соперника.

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

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

Первая строка входного файла содержит два целых числа N, M. Далее N пар чисел p_i, с_i  — описание боксёров из команды Пахома. Далее N пар чисел p_i, с_i  — описание команды соперников.

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

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

Ограничения

1 ≤ N ≤ 10⁶, 1 ≤ M ≤ 300, 1 ≤ с_i ≤ M; 1 ≤ p_i ≤ 10⁹.

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

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

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

3 1
1 1
2 1 
3 1
4 1
5 1
6 1

-9

4 2
60 1
100 2
110 2
120 2
200 1
50 2
40 2
30 2

12

3 3
5 1
10 2
15 3
6 1
11 2
16 3

-1