Đóng gói

Một xí nghiệp có một robot dùng để xếp các sản phẩm vào các thùng. Mọi thùng đều có dung tích như nhau. Có đúng hai thùng đang mở sẵn để robot xếp các sản phẩm vào. Mỗi thùng bất kỳ đều chứa được số sản phẩm mà tổng dung tích của chúng không vượt quá dung tích của thùng. Các sản phẩm lần lượt được đưa tới trên dãy băng theo đúng thứ tự. Robot có thể thực hiện các thao tác sau:

1. Đưa sản phẩm hiện tại trên dãy băng vào thùng \(1\).
2. Đưa sản phẩm hiện tại trên dãy băng vào thùng \(2\).
3. Đóng thùng \(1\) và mở một thùng mới thay thế cho thùng \(1\).
4. Đóng thùng \(2\) và mở một thùng mới thay thế cho thùng \(2\).

Các thao tác \(1, 2\) chỉ có thể thực hiện nếu tổng dung tích của sản phẩm cho vào và các sản phẩm đã có trong thùng không vượt quá dung tích của thùng. Một thùng được tính là đã dùng nếu nó chứa ít nhất một sản phẩm.

Yêu cầu: Cho biết dung tích mỗi thùng là \(L\), dung tích của \(N\) sản phẩm trên dãy băng theo thứ tự xuất hiện là \(a_1, a_2, \ldots, a_N\), hãy tìm số thùng ít nhất cần dùng để cho hết \(N\) sản phẩm vào thùng.

Input

• Dòng thứ nhất là hai số nguyên dương \(L\) và \(N\).
• Dòng tiếp theo chứa \(N\) số nguyên \(a_1, a_2, \ldots, a_N\) (\(1 \le a_i \le L\)).

Output

Gồm \(1\) số duy nhất là số thùng ít nhất cần dùng.

Scoring

• Subtask 1 (\(20\%\)): \(L \le 10^9\), \(N \le 20\).
• Subtask 2 (\(20\%\)): \(1 \le a_i \le 2\), \(L = 100\), \(N \le 10^6\).
• Subtask 3 (\(20\%\)): \(L \le 30\), \(N \le 10000\).
• Subtask 4 (\(20\%\)): \(L \le 5000\), \(N \le 100\).
• Subtask 5 (\(20\%\)): \(L \le 5000\), \(N \le 10000\).

Sample Input 1

3 5
1 1 1 3 1

Sample Output 1

3