Tích lũy đến mục tiêu (Accumulate Until Target)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mục tiêu nguyên dương $T$ và các khoản góp nguyên không âm. Từ tổng ban đầu 0, nhận các khoản góp theo thứ tự. Tìm số lượt ít nhất để tổng đạt hoặc vượt $T$; các khoản bằng 0 vẫn được tính là lượt nhận và không làm tăng tổng.

Input

Số đầu là $T$; theo sau là các khoản góp không âm. Bảo đảm khoản cuối cùng là khoản đầu tiên khiến tổng đạt hoặc vượt $T$; không có số sau đó.

Output

In số nguyên duy nhất: số lượt đọc nhỏ nhất để đạt mục tiêu.

Subtask

• Subtask 1 (20%): $1\le T\le100$, tối đa $5$ khoản góp trong $[0,100]$.
• Subtask 2 (30%): $1\le T\le10^6$, tối đa $100$ khoản góp trong $[0,10^6]$.
• Subtask 3 (50%): $1\le T\le10^{12}$, tối đa $100000$ khoản góp trong $[0,10^9]$.

Ví dụ

Ví dụ 1

Input

10
0 4 0 6

Output

4

Giải thích

Lần lượt tổng 0, 4, 4, 10; ba lượt đầu chưa đủ 10, lượt thứ tư đạt. Hai khoản 0 vẫn là hai lượt.

Ví dụ 2

Input

3
3

Output

1

Giải thích

Lượt đầu cộng 3 đạt đúng mục tiêu nên in 1.