Xét dãy số nguyên dương \(a_{1},\ a_{2},\ \ldots,\ a_{n}\ (1 \leq a_{i} \leq n)\). Một dãy chỉ số \(1 \leq i_{1} < i_{2} < \cdots < i_{k} \leq n\) mà \(a_{i_{1}} < a_{i_{2}}\ < \ \cdots\ < \ a_{i_{k}}\) thì dãy \(a_{i_{1}},\ a_{i_{2}},\ \ldots,\ a_{i_{k}}\) được gọi là một dãy con tăng của dãy 𝑎₁, 𝑎₂, …, 𝑎_𝑛 với độ dài của dãy là \(k\) và tổng \(a_{i_{1}},\ a_{i_{2}},\ \ldots,\ a_{i_{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 \(a_{1},\ a_{2},\ \ldots,\ a_{n}\) và số nguyên dương \(w\), hãy tìm dãy con tăng của dãy \(a_{1},\ a_{2},\ \ldots,\ a_{n}\) có độ dài lớn nhất và trọng số không vượt quá \(w\).

Dữ liệu:

+ Dòng đầu chứa hai số nguyên dương \(n,\ w\ (n\ \leq \ 50000)\)

+ Dòng thứ hai gồm \(n\) số nguyên dương \(a_{1},\ a_{2},\ \ldots,\ a_{n}\ (1\ \leq \ a_{i}\ \leq \ n)\)

Kết quả:

+ Một số nguyên là độ dài dãy con tăng lớn nhất tìm được thỏa mãn yêu cầu.

Ví dụ

Giới hạn: Đặt \(S\ = \ a_{1} + a_{2} + \cdots + a_{n}\ \)

+ Subtask 1: \(n \leq 20;\ w \leq \ S\);

+ Subtask 2: \(n\ \leq \ 50;\ w\ = \ S\);

+ Subtask 3: \(n\ \leq \ 50;\ w\ \leq \ S\);

+ Subtask 4: \(n\ \leq \ 500;w\ \leq \ S\);

+ Subtask 5: 𝑛 ≤ 50000; w = 𝑆;