EIU Programming Practices and Exams

Bạn A có N cuốn sách được đánh số từ 1 đến N. A muốn dành M giờ để đọc sách. A sẽ bắt đầu đọc từ 1 cuốn bất kì. Sau khi đọc xong cuốn i thì A sẽ đọc tiếp cuốn i + 1 , nếu đọc xong cuốn thứ N thì A sẽ đọc tiếp cuốn 1. A sẽ không đọc lại cuốn đã đọc. A muốn đọc càng nhiều sách càng tốt.

Cho thời gian để A đọc hết từng quyển sách, hỏi A có thể đọc tối đa bao nhiêu sách

Ví dụ: A có 5 cuốn sách, thời gian đọc xong từng cuốn là 10 10 15 4 5. A dành 22 giờ để đọc sách. A có thể đọc như sau:

Cách 1: đọc từ cuốn thứ nhất. A đọc được 2 cuốn đầu tiên tốn 20 giờ.

Cách 2: đọc từ cuốn thứ 2. A đọc được 1 cuốn hết 10 giờ.

Cách 3: đọc từ cuốn thứ 3. A đọc được 2 cuốn tốn 19 giờ.

Cách 4: đọc từ cuốn thứ 4. A đọc được 3 cuốn tốn 19 giờ (cuốn thứ 4, thứ 5 và cuốn đầu tiên).

Cách 5: đọc từ cuốn thứ 5. A đọc được 2 cuốn (cuốn thứ 5 và cuốn đầu tiên) tốn 15 giờ.

Vậy A có thể đọc tối đa 3 cuốn sách.

Input

Dòng đầu tiên là hai số nguyên n, m (n ≤ 10⁵, m ≤ 10⁹).

Dòng thứ hai là n số nguyên, trong đó số thứ i thể hiện thời gian A cần để đọc hết quyển sách thứ i..

Output

Số quyển sách tối đa A có thể đọc xong.

Example

Input:
5 20
10 10 15 4 5

Output:
3
Input:
6 100
5 3 7 8 10

Output:
5

Input:
5 15
4 5 4 8 9

Output:
3
Input:
5 3
4 5 4 5 5


Output:
0