Xét dãy số nguyên dương ~𝑎_1~, ~𝑎_2~, … , ~𝑎_𝑛~ (1 ≤ ~𝑎_𝑖~ ≤ ~𝑛~). Một dãy chỉ số 1 ≤ ~𝑖_1~ < ~𝑖_2~ < ⋯ < ~𝑖_𝑘~ ≤ ~𝑛~ mà ~𝑎_{𝑖1}~ < ~𝑎_{𝑖2}~ < ⋯ < ~𝑎_{𝑖k}~ thì dãy ~𝑎_{𝑖1}~ ,<~𝑎_{𝑖2}~, ......,~𝑎_{𝑖k}~ được gọi là một dãy con tăng của dãy ~𝑎_1~, ~𝑎_2~, … , ~𝑎_𝑛~ và tổng ~𝑎_{𝑖1}~ + ~𝑎_{𝑖2}~ + ⋯ +~𝑎_{𝑖k} ~ đượ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~, … , ~𝑎_𝑛~ .

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.

Vi du:

Input 1

5 10
4 2 3 1 5

Ouput 1

3

Input 2

5 5
4 2 3 1 5

Ouput 2

2

Gọi ~𝑆~ = ~𝑎_1~ + ~𝑎_2~ +… + ~𝑎_𝑛~

Subtask 1: ~𝑛~ ≤ 20; ~𝑊~ ≤ ~𝑆~; Subtask 2: ~𝑛~ ≤ 50; ~𝑊~ = ~𝑆~; Subtask 3: ~𝑛~ ≤ 50; ~𝑊~ ≤ ~𝑆~; Subtask 4: ~𝑛~ ≤ 500; ~𝑊~ ≤ ~𝑆~; Subtask 5: ~𝑛~ ≤ 50000; ~𝑊~ = ~𝑆~;