Задача A. Отбор ≡

Условие

Гриша участвует в отборе на стажировку в ***. Он не знает, на какой позиции он находится в таблице результатов, но знает, что в отборе участвует n претендентов. Кроме того, Гриша точно знает, что не менее a человек показали лучшие чем у Гриши результаты, и не более b человек написали отбор хуже, чем он.

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

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

Входные данные содержат три целых числа: n, a, b.

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

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

Ограничения

1 ≤ n ≤ 10⁴

0 ≤ a, b < n

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

3 1 1

2

5 2 3

3

Задача B. Генерация строки ≡

Условие

Требуется сгенерировать лексикографически минимальную строку состоящую из n букв "a", m букв "b" и k букв c. В искомой строке не должно быть двух подряд идущих букв "a", и для любых 4 подряд идущих букв должно встречаться не более одной буквы "c". На буквы "b" дополнительных ограничений нет.

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

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

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

Выходной файл должен содержать искомую строку длины n + m + k если такая строка существует, в противном случае строку "NO".

Ограничения

0 ≤ n, m, k ≤ 10⁵, 1 ≤ n + m + k ≤ 10⁵

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

Решения работающие для n + m + k ≤ 10 оцениваются из 50 баллов. Решения для k = 0 оцениваются из 40 баллов. Баллы выставляются за каждый успешно пройденный тест.

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

1 1 1

abc

10 3 1

NO

5 3 2

ababacabac

Задача 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