#893. WISEQ - Dãy con tăng trọng số

Xét dãy số nguyên dương . Một dãy chỉ số mà thì dãy được gọi là một dãy con tăng của dãy với độ dài của dãy là và tổng đượ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 và số nguyên dương , hãy tìm dãy con tăng của dãy có độ dài lớn nhất và trọng số không vượt quá .

Dữ liệu:

• Dòng đầu chứa hai số nguyên dương ;
• Dòng thứ hai gồm số nguyên dương .

Kết quả:

• Đưa ra một dòng chứa 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ụ:

Dữ liệu:

5 10
4 2 3 1 5

Kết quả:

3

Dữ liệu:

5 5
4 2 3 1 5

Kết quả:

2

Giới hạn:

Đặt

• Subtask ;
• Subtask ;
• Subtask ;
• Subtask ;
• Subtask ;