Trường THPT Chuyên Hoàng Văn Thụ - Hòa Bình

Một đoàn tàu có N toa (kể cả đầu máy) cần đi qua một chiếc cầu. Mỗi toa tàu dài 10m nhưng có trọng lượng khác nhau. Cây cầu dài 40m (như vậy tại một thời điểm nó có thể chứa được 4 toa tàu). Cầu sẽ bị gãy nếu tổng trọng lượng các toa tàu trên cầu tại một thời điểm là lớn hơn tải trọng của cầu. Các toa tàu được đánh số từ 1 đến N (đầu máy là toa số 1). Đoàn tàu qua cầu theo trật tự: toa số 1 qua trước tiên, sau đó là toa số 2, và cứ thế... đến toa thứ N.

Yêu cầu: Hãy tính số lượng tối đa các toa tàu có thể qua được cầu?

Input

• Dòng đầu chứa số W là tải trọng tối đa của cây cầu tại một thời điểm ( 1 ≤ W ≤ 10⁵).
• Dòng thứ hai chứa số nguyên dương N ( 1 ≤ N ≤ 15000) là số toa tàu (kể cả đầu máy)
• Dòng thứ i trong số N dòng tiếp theo chứa số nguyên C_i là trọng lượng của toa tàu thứ i (1 ≤ C_i ≤ 10⁵ với 1 ≤ i ≤ N).

Output

•  In ra số nguyên duy nhất là số toa tàu tối đa có thể qua cầu theo thứ tự đã nêu.

Example

Input:
100
6
50
30
10
10
40
50

Output:
5