Максимальна оцінка за кожну з чотирьох задач — 100 балів.
Для всіх задач:
обмеження на час — 1 секунда / тест;
обмеження на пам’ять — 256 МБ.

1. Письмо

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

На уроці письма й каліграфії Петрик один або кілька разів поспіль виписав у зошиті одне й те саме натуральне число. В результаті утворилося шестицифрове число n. Допоможіть учительці з’ясувати, яке найменше число міг виписувати Петрик.

Вхідні дані
У вхідному файлі вказане шестицифрове натуральне число n.

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

Приклади

2. Література

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

Щоб уникнути чергової двійки з літератури, Петрик має виконати домашнє завдання: вибрати з хрестоматії два різних твори загальним обсягом s сторінок і прочитати їх. Знаючи обсяг кожного з n творів, що є в хрестоматії, допоможіть хлопцю з’ясувати, скільки він має варіантів вибору.

Вхідні дані
У першому рядку вхідного файлу вказано натуральні числа s та n, не менші за 2. У другому рядку записано n натуральних чисел — обсяги (кількості сторінок) відповідних творів із хрестоматії. Усі числа у вхідному файлі (включно з числами s та n) не перевищують 200 000.

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

Приклади

Пояснення до прикладів
У першому прикладі Петрик може вибрати один із чотирьох варіантів:

• прочитати перший і другий твори з хрестоматії;
• або перший і четвертий;
• або другий і четвертий;
• або третій і п’ятий.

У другому прикладі жодні два твори не дають у сумі рівно 10 сторінок.


3. Фізкультура

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

На уроці фізкультури учні вишукувалися в шеренгу в деякому зручному для них порядку. Конче потрібно, однак, щоб усі стояли за зростом — у порядку від найвищого учня до найнижчого. Для цього вчитель може один або кілька разів зробити таке: назвати ім’я деякого учня і попросити його перейти в кінець шеренги. За яку найменшу кількість подібних дій учителю вдасться впорядкувати шеренгу бажаним чином?
Зріст кожного з n учнів відомий. Якщо кілька з них однакового зросту, то між собою такі учні в кінцевому розташуванні можуть стояти в довільному порядку (на вибір учителя). За бажання вчитель може переставляти одного й того самого учня кілька разів.

Вхідні дані
У першому рядку вхідного файлу вказано натуральне число n, не менше за 2 і не більше за 200 000. У другому рядку записано n натуральних чисел, що не перевищують 2·10⁹, — зріст кожного з n учнів у порядку, в якому вони стоять у шерензі на початку уроку.

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

Приклади

Пояснення до прикладів
У першому прикладі вчитель може діяти так: спочатку переставити в кінець шеренги першого з двох учнів зросту 134, далі переставити учня зросту 130, а потім — 126. Швидше ніж за три дії впорядкувати шеренгу вчителю не вдасться.
У другому прикладі учні відразу стоять у потрібному порядку. Переставляти нікого не потрібно.


4. Математика

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

Щоб заробити чергові дванадцять балів з математики, Петрик має розв’язати багато однотипних задач на переливання. Типова задача з Петрикового підручника виглядає так.
Є три порожні посудини місткістю a, b та c літрів. За одну операцію можна виконати якусь із трьох дій:

• повністю заповнити одну з посудин водою з джерела. До операції посудина може бути або порожньою, або вже частково наповненою. Кількість води у джерелі необмежена.

• вилити з однієї з посудин усю воду, що в ній міститься. До операції посудина не обов’язково має бути повністю заповненою.

• перелити з однієї посудини в іншу рівно стільки води, щоб або посудина, куди переливають воду, повністю заповнилася, або — якщо води для цього недостатньо — посудина, звідки переливають воду, спорожніла.

Операції кожного з трьох типів можна виконувати як завгодно багато разів. Треба з’ясувати, за яку найменшу кількість операцій і чи можливо взагалі «відміряти» n літрів, тобто зробити так, щоб принаймні в одній посудині опинилося рівно n літрів води.

Вхідні дані
У першому рядку вхідного файлу записано три натуральних числа a, b та c, а у другому рядку — натуральне число n. Усі чотири числа не перевищують 100.

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

Приклади

Пояснення до прикладів
У першому прикладі відміряти 7 літрів можна щонайменше за 4 кроки. Наприклад, таким чином:

1. Налити воду в 4-літрову посудину.
2. Перелити з неї усі 4 літри води в 6-літрову посудину.
3. Налити воду в 9-літрову посудину.
4. Перелити з неї 2 літри в 6-літрову посудину (та заповниться). У 9-літровій посудині залишиться рівно 7 літрів води.

У другому прикладі відміряти 1 літр можна щонайменше за 5 операцій. Приміром, так:

1. Налити воду в 10-літрову посудину.
2. Перелити з неї 3 літри в першу посудину.
3. Перелити з неї ж іще 3 літри в третю посудину. У 10-літровій посудині залишиться 4 літри води.
4. Вилити воду з першої 3-літрової посудини.
5. Перелити 3 літри води з 10-літрової посудини в порожню 3-літрову. У 10-літровій залишиться 1 літр.

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