Вам надано масив із ~n~ цілих чисел. Змініть масив так, щоб він не спадав, тобто кожен елемент був принаймні таким же великим, як і попередній.

За один хід ви можете збільшити значення будь-якого елемента на одиницю.

Яка найменша кількість ходів потрібна щоб упорядкувати масив згідно вимог?

Обмеження

~1 \le n \le 2 \cdot 10^5~

~1 \le x_i \le 10^9~

Input

Перший рядок містить ціле число ~n~ - розмір масиву.

Другий рядок містить ~n~ цілих чисел, розділених пропусками, ~x_1,x_2,\ldots,x_n~ - елементи масиву.

Output

Вивести шукану найменшу кількість ходів.

Sample Input 1

5
3 2 5 1 7

Sample Output 1

5

Notes

Треба виконати 1 хід для другого елемента (він стане рівним 3) і 4 ходи для четвертого(після цього дорівнюватиме 5). Оновлений масив буде таким:

3 3 5 5 7

Ми звикли виражати грошові суми в гривнях та копійках, проте в різні часи інші народи використовували зовсім інші системи. Наприклад, до 1971 року британський фунт стерлінгів дорівнював 4 кронам, або 20 шилінгам, або 60 гроутам, або 240 пенсам. Зрозуміло, що для переведення суми, вираженої в пенсах, у більші одиниці корисним буде ланцюжок співвідношень: 1 фунт стерлінгів = 4 крони; крона = 5 шилінгів; шилінг = 3 гроути; гроут = 4 пенси. Скориставшись ним можна дізнатись, що, наприклад, 1000 пенсів = 4 фунти стерлінгів 3 шилінги 1 гроут.

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

Input

У першому рядку записано ціле число ~S~ - сума, виражена в найменших грошових одиницях.

У другому рядку записано ціле число ~K~ - кількість рівнів у системі грошових одиниць.

У наступних ~K~ рядках записано по одному співвідношенню між грошовими одиницями (від найбільшої до найменшої) у форматі '~H~ ~M~ ~L~', де ~H~ і ~L~ - назви, відповідно, більшої і меншої грошових одиниць; ~M~ - ціле число, кількість менших одиниць у більшій.

Output

Вивести в один рядок суму, виражену в різних одиницях відповідно до умови.

Обмеження

~1 \le S \le 1000~

~1 \le K \le 10~

~1 \le M \le 100~

~1 \le |H|, |L| \le 15~

~H~, ~L~ містять символи з проміжку ['a'..'z']

Sample Input 1

100
2
kp 5 dz
dz 12 kop

Sample Output 1

1 kp 3 dz 4 kop

Sample Input 2

1000
2
kp 10 dz
dz 10 kop

Sample Output 2

10 kp

Sample Input 3

1000
4
poundsterling 4 crown
crown 5 shilling
shilling 3 groat
groat 4 penny

Sample Output 3

4 poundsterling 3 shilling 1 groat

Відомі співвідношення між різними грошовими одиницями.

Яка з грошових одиниць найдорожча?

Input

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

У наступних ~K~ рядках записано по одному співвідношенню між грошовими одиницями у форматі '~H~ ~M~ ~L~', де ~H~ і ~L~ - назви, відповідно, більшої і меншої грошових одиниць у вигляді рядка малих англійських букв кожна (до 15 символів); ~M~ - ціле число, кількість менших одиниць у більшій. Для кожної грошової одиниці ~H~ наведено не більше, ніж одне співвідношення. Найдорожча грошова одиниця дорожча від найдешевшої не більше ніж у ~2 \times 10^9~ разів.

Output

Вивести в один рядок назву найдорожчої грошової одиниці. Якщо таких грошових одиниць декілька, то вивести будь-яку назву.

Якщо відповідь відшукати неможливо, то вивести "there is no solution".

Обмеження

~1 \le K < 100~

~1 \le M \le 100~

~1 \le |H|, |L| \le 15~

~H~, ~L~ мiстять символи з промiжку ['a'..'z']

Sample Input 1

2
kp 5 dz
dz 12 kop

Sample Output 1

kp

Є ~n~ періодичних рядків з символів 'a', 'b', 'c', 'd', довжини не менше ~4~. Періодичний рядок - це будь-який підрядок (не тільки префікс) нескінченного рядка ~abcdabcdabcd...~ Підрядок - це набір послідовних сусідніх символів рядка у порядку зліва направо, можна уявити собі як символи даного рядка з ~l~-го по ~r~-й.

Для кожного з ~n~ рядків ми можемо обрати будь-який його підрядок (можливо, пустий) і об'єднати в будь-якому порядку так, щоб отримати префікс (тобто результат починається з 'a') рядка ~abcdabcdabcd....~ Назвемо це комбінацією рядків.

Потрібно порахувати найбільшу можливу довжину комбінації, що відповідає усім умовам.

Input

У першому рядку записано ціле число ~n~ - кількість рядків: ~(1 \le n \le 10^5)~

У наступних ~n~ рядках записано періодичні рядки (довжини не менше ніж ~4~) ~s_i~ ~(1 \le |s_i| \le 2*10^5)~

Гарантується, що сумарна довжина всіх періодичних рядків не перевищує ~10^6~ символів.

Output

У першому рядку виведіть ціле число ~ans~ — найбільшу можливу довжину комбінації, що відповідає усім умовам.

Sample Input 1

3
bcdabcd
abcd
abcdabc

Sample Output 1

16

• Виберемо з 'bcdabcd' підрядок 'dabcd'
• Виберемо з 'abcd' підрядок 'abcd'
• Виберемо з 'abcdabc' підрядок 'abcdabc'
• Об'єднаємо: 'abcdabc' + 'dabcd' + 'abcd' == 'abcdabcdabcdabcd'

Sample Input 2

2
abcd
bcdabcd

Sample Output 2

8

• Виберемо з 'abcd' підрядок 'abcd'
• Виберемо з 'bcdabcd' підрядок: 'abcd'
• Об'єднаємо 'abcd' + 'abcd' == 'abcdabcd' Зверніть увагу, не можна об'єднати 'bcdabcd' + 'abcd' == 'bcdabcdabcd', бо комбінація має починатись з 'a'.

Дано граф на ~n~ вершинах і ~m~ неорієнтованих, зважених ребрах. Кожне ребро розфарбовано в червоний або зелений кольори. Потрібно знайти цикл що містить вершини ~a~ і ~b~ дані в вхідних даних ~(a \ne b)~, і при цьому містить ребра обох кольорів. Виведіть найменшу можливу вагу такого циклу.

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

Вага циклу — це сума ваг його ребер.

Input

У першому рядку записано два цілі числа ~n~ і ~m~ — кількість вершин і ребер у графі: ~(1 \le n \le 10^5)~, ~(1 \le m \le 2*10^5)~

У другому рядку записано два цілі числа ~a~ і ~b~ — вершини, які має містити цикл: ~a \ne b~, ~(1 \le a,b \le n)~

У наступних ~m~ рядках міститься по чотири цілі числа ~u_i~ ~v_i~ ~w_i~ ~c_i~, які описують ребро, що з'єднує ~u_i~ i ~v_i~, з вагою ~w_i~, та кольором ~c_i~ (0 — червоний, 1 — зелений): ~(1 \le u_i,v_i \le n)~, ~(1 \le w_i \le 10^9)~, ~(0 \le c_i \le 1)~

Output

Виведіть одне ціле число — найменшу можливу вагу циклу, що містить вершини ~a~ і ~b~ і при цьому містить ребра обох кольорів.

Sample Input 1

7 8
1 4
1 2 1 0
2 3 1 0
3 4 1 0
4 5 1 0
5 6 1 0
6 1 1 0
1 7 1 1
7 6 1 0

Sample Output 1

7

Notes

Зверніть увагу, що без умови про те, що цикл має містити ребра обох кольорів, відповідь була б ~6~