Випробування автомата#122

Випробування автомата

1 second
512 megabytes
Medium

Фірма bookface, яка створена в Ужляндії, в якій працює Степан, вирішила встановити в своїх офісах автомати з продажу чаю та кави, щоб програмісти під час перерви могли з толком провести час.

Вартість склянки чаю та кави в автоматі передбачається встановити рівній п'яти ужикам (така в Ужляндії валюта). Автомати будуть приймати монети по 5 і 10 ужиків, а також купюри в 10, 50 і 100 ужиків. Коли програмісту потрібно видавати здачу (тобто коли програміст кинув у автомат монету в 10 ужиків, або купюру в 10, 50 або 100 ужиків), автомат видає здачу монетами в п'ять ужиків; якщо ж пасажир кинув у автомат монету в п'ять ужиків, то автомат її зберігає і може використовувати для здачі наступним програмістам.

Очевидно, що, щоб забезпечити можливість видачі здачі всім програмістам, може знадобитися спочатку завантажити в автомат деяку кількість монет в п'ять ужиків. Зараз в офісах фірми проходять випробування з метою визначити мінімальну кількість монет, які треба завантажити в автомат перед робочим днем.

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

Input

У першому рядку вхідного файлу знаходиться одне натуральне число - кількість покупок в автоматі, які були здійснені в ході випробування (1 \leq N \leq 50000). У другому рядку знаходяться натуральних чисел, кожне з яких рівне номіналу монети або купюри, яку використовував черговий програміст для оплати; кожен номінал може приймати одне з чотирьох значень: 5, 10, 50 або 100.

Output

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

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

У першому прикладі одна монета в п'ять ужиків буде потрібна для здачі першому програмісту і 19 монет - третьому, але під час здачі третьому можна використовувати ту монету, яку кине другий програміст, тому спочатку у автоматі досить 19 монет.

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

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