Cho dãy số ~A~ gồm ~N~ các số nguyên dương ~A_1,A_2,…,A_N~. Gọi dãy ~B~ là sự kết hợp của ~10^{100}~ dãy ~A~ ban đầu.

Yêu cầu: Tính tổng các số ít nhất của dãy ~B~ từ trái sang phải cho đến khi nào tổng đó vượt quá 1 số ~X~. Nói cách khác, hãy tìm 1 số nguyên k nhỏ nhất sao cho: ~∑_{i=1}^k~ ~B_i > X~.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên ~N~
• Dòng tiếp theo chứa ~N~ số nguyên ~A_i~
• Dòng cuối ghi giá trị ~X~.

Kết quả:

• Ghi một số nguyên là đáp án của bài toán.

Ràng buộc:

• ~1≤N≤10^5~
• ~1≤A_i ≤10^9~
• ~1≤X≤10^{18}~
• Tất cả các giá trị trong đầu vào là số nguyên.

Ví dụ:

Input

3
3 5 2
26 

Output

8 

Giải thích

Chúng ta có dãy ~B = (3,5,2,3,5,2,3,5,2, ......)~, với 8 phần tử đầu tiên của dãy ~B~ sẽ thỏa mãn yêu cầu của đề bài vì: ~∑_{i=1}^8~ ~B_i =28 > 26~.