Bình hay giúp đỡ ba mẹ làm việc nhà. Để bảo đảm việc học, Bình chỉ có thể sắp xếp được một lượng thời gian T để làm việc nhà. Bình liệt kê danh sách những việc nhà có thể làm, đi kèm với thời gian cần để thực hiện xong việc đó. Các việc nhà có thể thực hiện theo thứ tự bất kỳ; tại một thời điểm chỉ có thể thực hiện một việc nhất định. Hãy tìm cách làm sao để có thể hoàn thành được nhiều việc nhất trong danh sách của mình.

Yêu cầu: Cho các việc nhà và thời gian cần để hoàn thành, hãy viết chương trình cho biết số lượng việc nhà nhiều nhất có thể hoàn thành trong giới hạn thời gian T.

Input

Dòng thứ nhất chứa một số nguyên T (0 ≤ T ≤ 10⁹) – giới hạn tổng thời gian.
Dòng thứ hai chứa một số nguyên C (0 ≤ C ≤ 100) – số lượng việc nhà.
Tiếp theo có C dòng, mỗi dòng là một số nguyên dương biểu thị thời gian cần để hoàn thành một việc nhà (giả sử thời gian tối đa cho một việc ≤ 10⁹).

Output

Một số nguyên duy nhất – số lượng việc nhà nhiều nhất có thể hoàn thành trong thời gian T.

Ràng buộc: 50% số test có 0 ≤ T ≤ 10⁴ và thời gian tối đa để thực hiện một công việc là 10⁴.

Ví dụ

Input

6
3
1
2
6

Output

2

Giải thích: Có thể làm xong hai việc tốn 1 và 2 đơn vị thời gian (tổng 3 ≤ 6). Việc còn lại tốn 6 thời gian nên không kịp.