Ми маємо послідовність \(N\) натуральних чисел: \(A=(A_1,\dots,A_N)\). Нехай \(B\) — конкатенація \(10^{100}\) копій \(А\).

Розглянемо суму послідовності \(B\) зліва направо. Коли сума вперше перевищує \(X\)?

Іншими словами, знайдіть мінімальне ціле число \(k\) таке, що:

\(\displaystyle{\sum_{i=1}^{k} B_i \gt X}\).

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

Перший рядок містить ціле число \(N\) (\(1 \le N \le 10^5\))

Наступний  рядок містить \(N\) цілих чисел \(A_i\) (\(1 \le A_i \le 10^9\))

Останній рядок містить ціле число \(X\) (\(1 \le X \le 10^{18}\))

Числа у рядку розділяються пропуском. `

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

У вихідний потік виведіть шукане число.

Примітка

До прикладу 1:

Маємо B=(3,5,2,3,5,2,3,5,2,...).

\(\displaystyle{\sum_{i=1}^{8} B_i = 28 \gt 26} \) виконується коли kk дорівнює 8.

Приклад вхідних даних

3
3 5 2
26

Приклад вихідних даних

8

Приклад вхідних даних

4
12 34 56 78
1000

Приклад вихідних даних

23