1. Петрик П’яточкін рахує склади

Hазва програми: syllable.*

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

Вхідні дані
У вхідному файлі вказано натуральне число n, кількість складів для якого потрібно порахувати. Число n не перевищує 100.

Вихідні дані
Єдиний рядок вихідного файлу має містити кількість складів, які у своїй назві українською мовою має число n.

Приклади

Пояснення до прикладів
Слово «один» має два склади (містить дві голосні літери). Назва числа 25 — «двадцять п’ять» — має три склади (містить три голосні літери).

2. Петрик П’яточкін купує книги

Назва програми: books.*

Щоб краще підготуватися до різноманітних олімпіад, у яких бере участь, Петрик П’яточкін замовляє книги у зарубіжному інтернет-магазині. На жаль, Петрику доводиться платити не лише за самі книги, але також і за їх доставку в Україну: незалежно від кількості книг, доставлених хлопцю за один раз, Петрик платить за одну доставку d гривень. Крім того, українська митниця за одну доставку дозволяє безплатно провозити через кордон щонайбільше m книг. Якщо кількість книг перевищує m, митниця бере за кожну понаднормово завезену книгу t гривень мита. Перед олімпіадою з інформатики Петрик хоче купити в інтернет-магазині n книг. Він може замовити доставку всіх книг разом або як завгодно розподілити книги на довільну кількість окремих доставок. Допоможіть хлопцю визначити, яку найменшу загальну суму грошей він повинен витратити на доставки й на мито, щоб перевезти усі n книг в Україну.

Вхідні дані
У єдиному рядку вхідного файлу записані чотири натуральних числа n, d, m, t — відповідно кількість книг, які необхідно перевезти; вартість однієї доставки; найбільша кількість книг, яку можна перевезти без сплати мита; розмір мита за кожну понаднормово завезену книгу. Відомо, що n (d + t) < 2 · 10⁹ і m < 2 · 10⁹.

Вихідні дані
У вихідний файл виведіть єдине натуральне число — найменшу сумарну кількість грошей, яку має сплатити Петрик за доставку і як мито, щоб отримати замовлені в інтернет-магазині книги.

Приклади

Пояснення до прикладів
У першому прикладі потрібно перевезти 5 книг. Якщо замовити їх однією доставкою, доведеться сплатити 4 грн за доставку і за 5 – 3 = 2 понаднормово завезені книги по 6 грн, усього 16 грн. Якщо ж розподілити книги на дві доставки, наприклад 3 книги на першу і 2 книги на другу, треба буде сплатити 2 · 4 = 8 грн за дві доставки, зате під час жодної з доставок платити за понаднормово завезені книги не доведеться. Три чи більше доставок будуть коштувати явно більше за 8 грн, тому 8 грн — найменша сума, яку доведеться витратити.

У другому прикладі потрібно перевезти 3 книги. Якщо замовити їх однією доставкою, треба буде сплатити 2 + (3 – 2) · 1 = 3 грн. А за дві чи більше доставок доведеться заплатити вже не менше ніж 2 · 2 = 4 грн.

3. Петрик П’яточкін пише олімпіаду

Назва програми: olympiad.*

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

Вхідні дані
У першому рядку вхідного файлу вказано два натуральних числа n та m — кількість учасників районної олімпіади та кількість пар знайомих учасників, 2 ≤ n ≤ 1000. У кожному з наступних m рядків задано по два числа a_j й b_j — номери знайомих між собою учасників, 1 ≤ a_j < b_j ≤ n, 1 ≤ j ≤ m. Жодна пара номерів a_j й b_j не зустрічається у вхідному файлі більше ніж один раз. Крім того, вхідні дані гарантують, що є не більше ніж один спосіб розсадити учасників по двох кабінетах, щоб жодні два знайомі не сиділи в одному кабінеті.

Вихідні дані
У першому рядку вихідного файлу виведіть у порядку зростання номери учасників, які мають сидіти в кабінеті разом із учасником під номером 1 (Петриком П’яточкіним) включно із самим числом 1 (Петриком). У другому рядку виведіть у порядку зростання номери учасників, які повинні сидіти в іншому кабінеті.

Якщо жодне розташування учасників не задовольняє умову задачі, в обох рядках виведіть по нулю.

Приклади

Архів прикладів вхідних і вихідних файлів, згаданих в умовах задач, і відкомпільовану програму перевірки правильної взаємодії з системою тестування можна завантажити, натиснувши тут.