5 тур - з 14.11.16 по 20.11.2016

точка входу для відправлення розв'язків

http://134.249.159.199//cgi-bin/new-client?contest_id=37

Задача 1. Олімпіада з математики (20 балів)

Прокинувшись вранці, Петро Павлович вирішив замінити задачу складного рівня шкільної олімпіади з математики на досить просту (з метою отримання вищих результатів учнями). Прийшовши в школу, він написав умову задачі на аркуші в одному екземплярі та попросив учня Сашка до початку олімпіади зробити ще N копій. В його розпорядженні є два ксерокси, один з яких робить копію за х секунд, а другий – за y. (Дозволяється використовувати як один ксерокс, так і обидва одночасно; копію можна робити як з оригіналу, так і з копії). Допоможіть Сашкові з’ясувати, який мінімальний час йому буде потрібен, щоб виконати завдання вчителя.

Формат вхідних даних

У вхідному файлі записано три натуральних числа N, x и y, які розділені  пробілом (1 ≤ N ≤ 2∙10⁸, 1 ≤ x, y ≤ 10).

Формат вихідних даних

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

Наприклад,

Задача 2. Домашня робота з математики (100 балів)

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

Для кожного завдання Сашко визначив, скільки хвилин йому потрібно, щоб його виконати. Після цього Сашко зрозумів, що виконати всі завдання він точно не встигне. Отож він вирішив зробити всі завдання окрім одного – за одне невиконане завдання вчитель нічого не скаже.

Тепер Сашку слід вибрати, яке завдання не виконувати. Допоможіть Сашку вибрати завдання, яке можна не виконувати, щоб інші завдання виконати якомога швидше.

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

Перший рядок вхідного файлу містить цілі числа n и m — кількість завдань і кількість залежностей між завданнями (1 ≤ n ≤ 100, 0 ≤ m ≤ 1000). Другий рядок містить n цілих чисел: t1, t2, . . . , tn. Число ti означає кількість хвилин, необхідних Сашку для виконання i-го завдання (1 ≤ ti ≤ 1000). Далі іде m рядків, кожен з яких містить два цілих числа. Числа a и b означають, що

завдання a слід виконати раніше аніж завдання b. Гарантується, що всі завдання можна виконати.

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

Вивести одне число – мінімальну кількість хвилин, необхідних Сашку для виконання всіх завдань крім одного.

Наприклад

В даному прикладі Сашко може не виконувати четверте завдання. Всі інші завдання він виконає за 11 хвилин.