Ims, Master of Accessories

Interview

Time limit1sMemory limit1024 MB

Summary

Given current fatigue P and N accessories with fatigue costs A_i, find the most accessories Ims can craft while fatigue is under 200 before each craft.

Level: Easy3 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

MapleStory has a crafting system called Professional Skills. Professional Skills let you craft a variety of equipment and elixirs, and in exchange, a set amount of fatigue builds up. Ims, a master of accessory crafting, wants to know how to craft as many accessories as possible more efficiently.

There are $N$ accessories that Ims can make, and crafting each one adds $A_i$ fatigue.

Ims can craft an accessory when the accumulated fatigue is less than $200$ . If the current accumulated fatigue is $P$ , find the maximum number of accessories Ims can craft!

Input

The first line contains two integers $P$ and $N$ , separated by a space. ( $1 \le P \le 200$ , $1 \le N \le 1\,000$ )

The second line contains integers $A_1, A_2, \dots, A_N$ , separated by spaces. ( $1 \le A_i \le 200$ )

Output

Print the maximum number of accessories that can be crafted.

Examples2

Example 1
Input
```
190 5
20 1 8 1 10
```
Expected output
```
3
```
Example 2
Input
```
195 4
20 1 8 1
```
Expected output
```
3
```