Xét dãy số nguyên dương 𝑎1, 𝑎2, … , 𝑎𝑛 (1 ≤ 𝑎𝑖 ≤ 𝑛). Một dãy chỉ số 1 ≤ 𝑖1 < 𝑖2 < ⋯ < 𝑖𝑘 ≤ 𝑛 mà 𝑎𝑖1 < 𝑎𝑖2 < ⋯ < 𝑎𝑖𝑘 thì dãy 𝑎𝑖1 , 𝑎𝑖2 , … , 𝑎𝑖𝑘 được gọi là một dãy con tăng của dãy 𝑎[1], 𝑎[2], … , 𝑎[𝑛] và tổng 𝑎[𝑖1] + 𝑎[𝑖2] + ⋯ + 𝑎[𝑖𝑘 ]được gọi là trọng số của dãy con tăng.

Yêu cầu: Cho dãy số nguyên dương 𝑎1, 𝑎2, … , 𝑎𝑛 và số nguyên dương 𝑊, hãy tìm dãy con tăng của dãy 𝑎1, 𝑎2, … , 𝑎𝑛 có độ dài lớn nhất và trọng số không vượt quá 𝑊.

Input

• Dòng đầu chứa hai số nguyên dương 𝑛, 𝑊;
• Dòng thứ hai gồm 𝑛 số nguyên dương 𝑎1, 𝑎2, … , 𝑎𝑛. (1 ≤ ai ≤ 10^6)

Output

• Gồm một dòng chứa một số là độ dài dãy con tăng lớn nhất tìm được thỏa mãn.

Sample Input

5 10 
4 2 3 1 5

Sample Output

3

Giới hạn

Gọi 𝑆 = 𝑎1 + 𝑎2 + ⋯ + 𝑎𝑛 
Subtask 1: 𝑛 ≤ 20; 𝑊 ≤ 𝑆; 
Subtask 2: 𝑛 ≤ 50; 𝑊 = 𝑆; 
Subtask 3: 𝑛 ≤ 50; 𝑊 ≤ 𝑆; 
Subtask 4: 𝑛 ≤ 500; 𝑊 ≤ 𝑆; 
Subtask 5: 𝑛 ≤ 50000; 𝑊 = 𝑆;
Trong tất cả các test có W< S thì n*W ≤ 10^6