408713: GYM103270 C Abhilash's Dog

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Abhilash's Dogtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Abhilash's dog Brian woke up late today, and there's only $$$m$$$ minutes left until his first class at Doge University starts! He needs to do many tasks before the first class starts. Sadly, Brian will probably not be able to finish all of his tasks. Brian is very efficient however, and can start the next task immediately after the previous, and can join class on Zoom at any point. This means that if Brian can finish a task just as class is about to start at time $$$m$$$, that task can be done. Given that he must do $$$n$$$ tasks in order, where each task $$$i$$$ takes $$$t_i$$$ minutes to complete, determine exactly how many tasks Brian can finish before his first class starts!

Input

The first line of the input contains $$$m (0 \le m \le 10^8)$$$, the number of minutes left until Brian's first class.

The next line of the input will contain $$$n (1 \le n \le 10^3)$$$, the number of tasks Brian needs to do.

The next $$$n$$$ lines of the input will each contain an integer $$$t_i (1 \le t_i \le 10^5)$$$, the amount of time it takes Brian to complete the $$$i^{th}$$$ task.

Output

A single integer, the number of tasks Brian can fully complete before his first class starts. If Brian can only partially finish a task, that does not count.

ExamplesInput
5
4
1
2
3
4
Output
2
Input
0
4
1
2
3
4
Output
0
Input
10
4
1
2
3
4
Output
4

加入题单

上一题 下一题 算法标签: