Số dương đạt ngưỡng (Positive Contributions to a 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à một luồng các khoản góp nguyên dương. Bắt đầu với tổng bằng $0$, nhận các khoản góp theo đúng thứ tự. Tìm số khoản góp đầu tiên ít nhất để tổng tích lũy lớn hơn hoặc bằng $T$. Ngừng ngay tại khoản góp đầu tiên khiến tổng đạt ngưỡng.

Input

Số đầu tiên là $T$. Theo sau là các khoản góp nguyên dương, phân tách bằng khoảng trắng hoặc xuống dòng. Bảo đảm tổng đạt $T$ đúng khi đọc giá trị cuối cùng; không có giá trị sau lượt đạt ngưỡng.

Output

In một số nguyên: số lượt nhận cần thiết nhỏ nhất để tổng đạt ít nhất $T$.

Subtask

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

Ví dụ

Ví dụ 1

Input

12
3 4 5

Output

3

Giải thích

Tổng khởi đầu 0. Sau góp 3: tổng 3 < 12; sau góp 4: tổng 7 < 12; sau góp 5: tổng 12 ≥ 12. Lần đầu đạt là lượt thứ ba.

Ví dụ 2

Input

5
9

Output

1

Giải thích

Khoản góp đầu tiên 9 đã lớn hơn hoặc bằng ngưỡng 5; vẫn phải thực hiện một lượt đọc và in 1.