Xe tăng là một phương tiện có cách di chuyển rất đặc biệt. Các bánh xe của nó trải dài trên nền đất để tăng diện tích tiếp xúc, từ đó giảm áp lực lên nền. Giả sử xe tăng đang muốn đi từ ~A~ đến ~B~, ta có thể chia đoạn đất này thành ~n~ đoạn nhỏ, đoạn thứ ~i~ có độ cứng ~a_i~. Một xe tăng chiều dài ~L~, khối lượng ~M~ có thể đi qua nếu tại mọi thời điểm, nó luôn đứng trên vùng đất có tổng độ cứng lớn hơn ~M~ (có nghĩa là mọi đoạn con liên tiếp độ dài ~L~ của dãy ~a~ đều phải có tổng lớn hơn hoặc bằng ~M~).

Yêu cầu: Cho biết khối lượng ~M~ của xe tăng, độ cứng của ~n~ đoạn nhỏ của vùng đất từ ~A~ đến ~B~, hãy tính chiều dài ~L~ nhỏ nhất có thể có của nó để xe tăng đi qua được vùng đất này.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên ~M~ và ~n~;
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~, với ~a_i~ là độ cứng của đoạn thứ ~i~ (~1 \le i \le n~) trong vùng đất từ ~A~ đến ~B~.

Dữ liệu đảm bảo tổng của mảng ~a~ lớn hơn hoặc bằng ~M~.

Kết quả

• Ghi một số nguyên duy nhất là chiều dài ngắn nhất có thể của xe tăng.

Ví dụ

Đầu vào:

6 5
3 2 1 4 5

Đầu ra:

3

Giải thích: Với ~L = 3~, mọi đoạn con gồm ~3~ đoạn liên tiếp có tổng lần lượt là ~6~, ~7~, ~10~, đều không nhỏ hơn ~M = 6~. Với ~L = 2~, đoạn con ~3 + 2 = 5 < 6~ nên xe tăng không đi qua được.

Giới hạn

• ~1 \le a_i \le 10^9~, ~1 \le M \le 10^9~

Điểm của một subtask chỉ được tính khi tất cả các test thuộc subtask đó đều đúng.