Positive Contributions to a Target

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given a positive target $T$ and a stream of positive integer contributions, start with cumulative total zero and receive contributions in their given order. Find the minimum number of initial contributions whose sum is at least $T$. Stop immediately upon reaching the target.

Input

The first integer is the target $T$. It is followed by positive contributions, separated by whitespace. The target is first reached after reading the final contribution; no additional value follows.

Output

Print one integer: the smallest number of contributions needed to reach or exceed $T$.

Subtasks

• Subtask 1 (20%): $1\le T\le100$; at most $5$ contributions, each in $[1,100]$.
• Subtask 2 (30%): $1\le T\le10^6$; at most $100$ contributions, each in $[1,10^6]$.
• Subtask 3 (50%): $1\le T\le10^{12}$; at most $100000$ contributions, each in $[1,10^9]$.

Examples

Example 1

Input

12
3 4 5

Output

3

Explanation

Totals after contributions are 3, 7 and 12. The target 12 is first reached at contribution three.

Example 2

Input

5
9

Output

1

Explanation

The first contribution 9 already exceeds 5, so exactly one contribution is needed.