Có ~N~ đồ vật được đánh số từ ~1~ đến ~N~. Đồ vật thứ ~i~ (~1 \leq i \leq N~) có khối lượng là ~w_i~ và giá trị là ~v_i~.

Taro quyết định chọn một số đồ vật bỏ vào chiếc túi của anh mang về. Sức chứa tối đa của chiếc túi là ~W~, nghĩa là tổng khối lượng các đồ vật có thể mang tối đa là ~W~.

Hãy tìm tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.

Lưu ý: Bài tập dưới đây bạn cần giải riêng ~3~ trường hợp (do ~3~ subtask này có giới hạn khác nhau). Dưới đây là code mẫu có thể follow theo

const int MAXN = 105;
int n, W;
int v[MAXN], w[MAXN];
namespace Subtask1 {
    bool check() {
        return n <= 20;
    }

    void solve() {}
}

namespace Subtask2 {
    bool check() {
        if (n > 100 || W > 100000) return false;
        return false;
    }

    void solve() {}
}

namespace Subtask3 {
    bool check() {
        if (n > 100) return false;
        bool check = true;
        for (int i = 1; i <= n; i++) {
            check &= (v[i] <= 1000);
        }
        return check;
    }

    void solve() {}
}

int main() {
    // Nhập input
    cin >> n >> W;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }

    if (Subtask1::check()) Subtask1::solve();
    else if (Subtask2::check()) Subtask2::solve();
    else {
        Subtask3::solve();
    }
}

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~W~: số lượng đồ vật và sức chứa tối đa của chiếc túi.
• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~w_i~ (~1 \leq w_i \leq W~) và ~v_i~ lần lượt là khối lượng và giá trị của đồ vật thứ ~i~.

Output

• Xuất ra tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.

Scoring

• Subtask ~1~ (~40\%~ số điểm): ~N \le 20~, ~1 \le W, V_i \le 10^9~.
• Subtask ~2~ (~30\%~ số điểm): ~N \le 100, 1 \le W \le 10^5, v_i \le 10^9~.
• Subtask ~3~ (~30\%~ số điểm): ~N \le 100, 1 \le W \le 10^9, 1 \le v_i \le 10^3~.

Example

Sample Input

3 8
3 30
4 50
5 60

Sample Output

90

Note

Chọn đồ vật ~1~ và ~3~. Tổng khối lượng sẽ là ~30+60=90~.

Có ~N~ nhóm đồ vật được đánh số từ ~1~ đến ~N~. Nhóm vật thứ ~i~ (~1 \leq i \leq N~) gồm vô hạn đồ vật, mỗi đồ vật có khối lượng là ~w_i~ và giá trị là ~v_i~ (bạn có thể chọn ~0~ hoặc nhiều đồ vật thuộc nhóm này).

Taro quyết định chọn một số đồ vật bỏ vào chiếc túi của anh mang về. Sức chứa tối đa của chiếc túi là ~W~, nghĩa là tổng khối lượng các đồ vật có thể mang tối đa là ~W~.

Hãy tìm tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~W~: số lượng đồ vật và sức chứa tối đa của chiếc túi.
• ~N~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~w_i~ (~1 \leq w_i \leq W~) và ~v_i~ lần lượt là khối lượng và giá trị của đồ vật thứ ~i~.

Output

• Xuất ra tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.

Constraints

• ~N \le 100~
• ~W \le 10^5~
• ~1 \le w_i \le W~
• ~1 \le v_i \le 10^9~

• Sample Input

2 7
2 3
3 4

Sample Output

10

Cho dãy ~a~ gồm ~n~ phần tử nguyên dương. Hãy đếm số tổng khác nhau có thể tạo ra từ các dãy con không nhất thiết liên tiếp của ~a~ (không tính dãy rỗng).

Input

• Dòng thứ nhất chứa số nguyên dương ~n~ miêu tả số phần tử trong dãy.
• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~a~.

Output

• Gồm một số nguyên dương miêu tả kết quả bài toán.

Constraints

• ~1 \le n \le 1000~
• ~0 < a_i \le 1000~.

Subtasks

• Subtask ~1~: ~n \le 20~ ~(30\%)~
• Subtask ~2~: ~n \le 50~ ~(40\%)~
• Subtask ~3~: Không có ràng buộc gì thêm ~(30\%)~

Sample Input 1:

3
1 4 5

Sample Output 1:

6

Sample Input 2:

4
1 1 1 1 

Sample Output 2:

4

Có ~N~ nhóm đồ vật được đánh số từ ~1~ đến ~N~. Nhóm vật thứ ~i~ (~1 \leq i \leq N~) gồm ~k_i~ đồ vật, mỗi đồ vật có khối lượng là ~w_i~ và giá trị là ~v_i~ (bạn có thể chọn ~0~ hoặc nhiều đồ vật thuộc nhóm này, tối đa là ~k_i~).

Taro quyết định chọn một số đồ vật bỏ vào chiếc túi của anh mang về. Sức chứa tối đa của chiếc túi là ~W~, nghĩa là tổng khối lượng các đồ vật có thể mang tối đa là ~W~.

Hãy tìm tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~W~: số lượng đồ vật và sức chứa tối đa của chiếc túi.
• ~N~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~k_i~, ~w_i~ (~1 \leq w_i \leq W~) và ~v_i~ lần lượt là khối lượng và giá trị của đồ vật thứ ~i~.

Output

• Xuất ra tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.

Constraints

• ~N \le 100~
• ~W \le 10^4~
• ~1 \le w_i \le W~
• ~1 \le v_i \le 10^9~

Sample Input

3 10
2 3 5
3 2 3
1 5 10

Sample Output

18

Một trò chơi có luật chơi như sau: Người chơi ban đầu có ~W~ năng lượng và trò chơi có ~N~ màn chơi, màn chơi thứ ~i~ có các thông tin như sau:

• Năng lượng của màn chơi là ~m_i~ - mỗi khi chơi màn này, năng lượng sẽ giảm đi ~m_i~;
• Điểm kinh nghiệm của màn chơi là ~e_i~ - người chơi thu được ~e_i~ điểm kinh nghiệm;
• Trừ điểm kinh nghiệm khi chơi lại là ~s_i~ - mỗi khi chơi lại màn này, số điểm kinh nghiệm nhận được sẽ bị giảm đi ~s_i \times (k - 1)~ (với ~k~ là số lần chơi màn này). Tức là, số điểm kinh nghiệm thu được khi chơi màn chơi thứ ~i~ tại lần thứ ~k~ là ~e_i - s_i \times (k - 1)~;
• Có thể chọn các màn chơi không cần theo thứ tự. Năng lượng của người chơi phải lớn hơn hoặc bằng năng lượng của màn chơi thì mới chơi được màn chơi đó.

Yêu cầu: Đưa ra tổng điểm kinh nghiệm lớn nhất có thể thu được khi chơi trò chơi trên.

Dữ liệu vào từ tệp văn bản GAME.INP:

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~W~ ~(N \le 2 \times 10^5;~ ~W \le 3000)~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~m_i, e_i, s_i~ ~(1 \le i \le N; \ m_i \le 3000; \ s_i \le e_i \le 10^5)~.

Kết quả ghi ra tệp văn bản GAME.OUT:

Gồm một số nguyên duy nhất là tổng điểm kinh nghiệm lớn nhất thu được thoả mãn yêu cầu đề bài.

Ví dụ

Input

2 10
2 6 2
5 5 5

Output

15

Giải thích

• Lần ~1~: Chơi màn chơi thứ ~1~: Mất ~2~ năng lượng, điểm kinh nghiệm thu được là ~6~;
• Lần ~2~: Chơi màn chơi thứ ~2~: Mất ~5~ năng lượng, điểm kinh nghiệm thu được là ~5~;
• Lần ~3~: Chơi lại màn chơi thứ ~1~: Mất ~2~ năng lượng, điểm kinh nghiệm thu được là ~4~;

~\Rightarrow~ Vậy mất tổng cộng ~9~ năng lượng và tổng điểm kinh nghiệm thu được là ~15~.

Input

2 8
3 4 2
2 3 1

Output

9

Giải thích

• Lần ~1~: Chơi màn chơi thứ ~1~: Mất ~3~ năng lượng, điểm kinh nghiệm thu được là ~4~;
• Lần ~2~: Chơi lại màn chơi thứ ~1~: Mất ~3~ năng lượng, điểm kinh nghiệm thu được là ~2~;
• Lần ~3~: Chơi màn chơi thứ ~2~: Mất ~2~ năng lượng, điểm kinh nghiệm thu được là ~3~;

~\Rightarrow~ Vậy mất tổng cộng ~8~ năng lượng và tổng điểm kinh nghiệm thu được là ~9~.

Ràng buộc

• Có ~30\%~ số test ứng với ~30\%~ số điểm có ~N \le 2; \ W \le 20~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~N, W \le 300~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~N \le 1000~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có năng lượng của màn chơi là như nhau;
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm không có ràng buộc gì thêm.

Lê là người thắng cuộc trong cuộc thi "Thiết kế thuật toán nén dữ liệu" và được nhận các phần thưởng của Ban tổ chức. Ban tổ chức đã chuẩn bị n món quà, các món quà được đánh số từ ~0~ đến ~n - 1~, món quà thứ ~i~ (~0 \le i < n~) có giá trị là một số nguyên dương ~v_i~ và Lê được chọn lấy một số món quà nhưng tổng giá trị các món quà không được vượt quá ~S~. Để việc chọn các món quà thêm phần thú vị, Ban tổ chức đưa ra cách thức chọn quà như sau:

• Ban tổ chức công khai giá trị của từng món quà nhưng không cho Lê biết giá trị ~S~.

• Lê được thực hiện không quá ~t~ lượt chọn quà, ở lượt thứ ~r~ (~0 \le r < t~), Lê cần đưa ra một dãy số ~p_0,p_1,\ldots,p_{n-1}~ là hoán vị của ~0, 1,\ldots,n- 1~ thể hiện thứ tự ưu tiên chọn các món quà. Khi đó, Ban tổ chức sẽ cho Lê biết số món quà mà Lê có thể nhận được nếu ưu tiên lấy các món quà theo thứ tự đó. Cụ thể, Ban tổ chức sẽ cho Lê biết giá trị ~c~ lớn nhất mà ~v_{p_0}+v_{p_1}+\ldots+v_{p_{c-1}}\le S~ hoặc thông báo ~c = 0~ nếu không lấy được món quà nào.

• Sau khi thực hiện một số lượt không vượt quá ~t~, Lê có thể dừng và được phép chọn các món quà ở một lượt nào đó mà tổng giá trị các món quà ở lượt đó là lớn nhất trong các lượt đã thực hiện.

Yêu cầu: Hãy giúp Lê đưa ra cách chọn quà sao cho tổng giá trị các món quà được nhận là lớn nhất.

Input

Thí sinh cần cài đặt hàm: void run(int n, vector<int> v, int t), trong đó:

• ~n~ là số món quà;

• ~v~ là vector chứa thông tin về giá trị các món quà với ~v[i]~ là giá trị món quà thứ ~i~;

• ~t~ là số lượt cho phép;

Hàm trên có thể gọi đến hàm sau: int select(vector<int> p), trong đó:

• ~p~ là một hoán vị của dãy ~0,1,\ldots,n-1~;

• hàm này trả về số lượng món quà lấy được nếu ưu tiên lấy các món quà theo thứ tự mô tả bởi hoán vị ~p~;

• hàm này không được gọi quá ~t~ lần.

Trong chương trình thí sinh cần phải khai báo thư viện bằng dòng lệnh #include "bonuslib.h" ở đầu chương trình. Ngoài ra, thí sinh được phép khai báo thêm thư viện, xây dựng các hàm, sử dụng biến toàn cục khác nếu cần.

Scoring

Có tất cả ~6~ subtask. Với mỗi test trong mỗi subtask, luôn tồn tại phương án chọn để tổng giá trị bằng đúng và phần trăm số điểm cho mỗi test được tính như sau:

• Thí sinh sẽ nhận được ~0\%~ số điểm nếu:

  • chạy sinh lỗi;

  • tương tác sai quy cách;

  • chạy quá thời gian;

  • hàm select được gọi quá ~t~ lần;

• Ngược lại, gọi ~TS~ là tổng giá trị của các món quà trong cách chọn của thí sinh, ~GK~ là tổng giá trị của các món quà trong cách chọn của giám khảo, khi đó phần trăm số điểm của test là:

  • ~0\%~ nếu ~Q>1~;

  • ~100\%~ nếu ~Q<0~;

  • ~100\%\times (-\log\_{10}(0.9\times Q+0.1))~ nếu ~0\le Q\le 1~;

  với ~Q=2\times n\times \dfrac{GK-TS}{GK}~.

Với mỗi subtask, gọi ~e~ là phần trăm số điểm nhỏ nhất của một test mà thí sinh đạt được trong các test thuộc subtask, ~score~ là điểm của subtask, khi đó, điểm cho subtask được tính bằng ~e\times score~.

Notes

Giả sử có ~4~ món đồ với giá trị tương ứng là ~\{9,3,1,5\}~ và ~t=3~, ~S=8~, hàm run sẽ được gọi với giá trị các tham số tương ứng là run(4,9,3,1,5,3). Dưới đây là một ví dụ cách gọi lần lượt các hàm select: