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.

Có ~n~ đồ vật được đánh số từ ~1~ tới ~n~. Đồ vật thứ ~i~ có trọng lượng là ~w_i~ và có giá trị là ~v_i~.

Bạn cần trả lời ~q~ truy vấn, truy vấn thứ ~i~ gồm ba số nguyên ~l_i~, ~r_i~ , ~W_i~, hỏi rằng giả sử nếu chỉ xét các đồ vật trong đoạn ~[l_i,r_i]~, thì với tổng trọng lượng tối đa là ~W_i~, bạn có thể thu được tổng giá trị lớn nhất là bao nhiêu? Biết rằng mỗi đồ vật trong đoạn đó bạn chỉ có thể lấy tối đa một lần.

Input

• Dòng đầu gồm số nguyên dương ~n~ ~(1 \le n \le 10^4)~
• ~n~ dòng sau, dòng thứ ~i~ gồm hai số nguyên dương miêu tả đồ vật thứ ~i~: ~w_i~ và ~c_i~ ~(1 \le w_i \le 100, c_i \le 10^4)~.
• Dòng tiếp theo gồm số nguyên dương ~q~ miêu tả số truy vấn ~(q \le 10^5)~.
• ~q~ dòng sau, dòng thứ ~i~ gồm ba số nguyên dương miêu tả truy vấn thứ ~i~: ~l_i~, ~r_i~, ~W_i~ ~(1 \le l_i \le r_i \le n; 1 \le W_i \le 100)~.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.

Subtask

• Subtask ~1~: ~r-l \le 100~ ~(40\%)~
• Subtask ~2~: ~q \le 10^4~ ~(30\%)~
• Subtask ~3~: Không giới hạn gì thêm ~(30\%)~

Example

Sample Input 1

4
2 15
2 20
4 36
1 4
3
1 2 4
1 4 7
3 4 2

Sample Output 1

35
60
4

Một xí nghiệp có một robot dùng để xếp các sản phẩm vào các thùng. Mọi thùng đều có dung tích như nhau. Có đúng hai thùng đang mở sẵn để robot xếp các sản phẩm vào. Mỗi thùng bất kỳ đều chứa được số sản phẩm mà tổng dung tích của chúng không vượt quá dung tích của thùng. Robot có thể thực hiện các thao tác sau:

• Đưa một sản phẩm hiện tại trên dãy băng vào thùng ~1~,
• Đưa một sản phẩm hiện tại trên dãy băng vào thùng ~2~,
• Đóng thùng ~1~ và mở một thùng mới thay thế cho thùng ~1~,
• Đóng thùng ~2~ và mở một thùng mới thay thế cho thùng ~2~.

Các thao tác 1, 2 chỉ có thể thực hiện nếu tổng dung tích của sản phẩm cho vào và các sản phẩm đã có trong thùng không vượt quá dung tích của thùng.

Yêu cầu: Cho biết dung tích mỗi thùng là ~𝑊~, dung tích của ~𝑛 sản~ phẩm trên dãy băng theo thứ tự xuất hiện là ~𝑎_1, 𝑎_2, . . . , 𝑎_𝑛~ , hãy tìm số thùng ít nhất để có thể cho ~𝑛~ sản phẩm vào thùng.

Input

• Dòng thứ nhất là hai số nguyên ~𝑊~ và ~𝑛~;
• Dòng tiếp theo chứa các số mô tả các số ~𝑎_1, 𝑎_2, … , 𝑎_𝑛~.

Output

• Gồm một số duy nhất là số thùng ít nhất cần dùng.

Input

8 6
4 2 5 3 5 4

Output

3

Giải thích

• Đưa ~1~ vào thùng ~1~
• Đưa ~2~ ~3~ ~4~ ~5~ vào thùng ~2~ (cần mở thêm một thùng)
• Đưa ~6~ vào thùng ~1~ (vẫn còn đủ chỗ, không cần mở thêm)

Ràng buộc

• Subtask 1 [10 tests] ~𝑊 ≤ 10^9 ; 𝑛 ≤ 20~
• Subtask 2 [10 tests] ~1 ≤ 𝑎_𝑖 ≤ 2; 𝑊 = 100; 𝑛 ≤ 10^6~
• Subtask 3 [10 tests] ~𝑊 ≤ 30; 𝑛 ≤ 10000~
• Subtask 4 [10 tests] ~𝑊 ≤ 5000; 𝑛 ≤ 100~
• Subtask 5 [10 tests] ~𝑊 ≤ 5000 ; 𝑛 ≤ 10000~

Mikoto đang ở trong một mê cung được biểu diễn bởi một bảng vuông gồm ~N~ hàng và ~N~ cột. Mỗi ô hoặc là ô trống, hoặc là ô bị chặn.

Ô nằm ở hàng ~i~, cột ~j~ được ký hiệu là ~(i, j)~ với ~1 <= i, j <= N~.

Ban đầu, Mikoto đứng tại ô ~(sx, sy)~ và muốn đi tới ô đích ~(gx, gy)~. Hai ô này luôn là ô trống.

Mikoto có thể thực hiện các thao tác sau, theo thứ tự bất kỳ, không giới hạn số lần:

• Bắn railgun theo hàng hiện tại: toàn bộ các ô trong hàng đang đứng sẽ trở thành ô trống. Thao tác này tốn ~A~ đơn vị thời gian.
• Bắn railgun theo cột hiện tại: toàn bộ các ô trong cột đang đứng sẽ trở thành ô trống. Thao tác này tốn ~A~ đơn vị thời gian.
• Đi bộ sang một ô kề cạnh đang trống: từ ~(x, y)~ có thể sang một trong bốn ô ~(x - 1, y)~, ~(x + 1, y)~, ~(x, y - 1)~, ~(x, y + 1)~ nếu ô đó nằm trong bảng. Thao tác này tốn ~B~ đơn vị thời gian.

Lưu ý rằng sau khi một hàng hoặc một cột bị bắn railgun, mọi ô trên hàng hoặc cột đó sẽ được xem là ô trống cho các bước di chuyển tiếp theo.

Do thể trạng mỗi ngày khác nhau, Mikoto muốn xét ~Q~ kịch bản. Ở kịch bản thứ ~i~, chi phí bắn railgun và đi bộ lần lượt là ~(ai, bi)~.

Với mỗi kịch bản, hãy tính thời gian nhỏ nhất để Mikoto đi từ ~(sx, sy)~ tới ~(gx, gy)~.

Input

• Dòng đầu chứa số nguyên ~N~.
• Dòng thứ hai chứa ~4~ số nguyên ~sx~, ~sy~, ~gx~, ~gy~.
• ~N~ dòng tiếp theo, mỗi dòng là một xâu độ dài ~N~ chỉ gồm:
  • ~.~: ô trống
  • ~\#~: ô bị chặn
• Dòng tiếp theo chứa số nguyên ~Q~.
• ~Q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~ai~, ~bi~.

Output

• In ra ~Q~ dòng.
• Dòng thứ ~i~ là đáp án cho kịch bản thứ ~i~: thời gian nhỏ nhất để đi từ ô xuất phát tới ô đích.

Subtask

• Subtask 1: ~N <= 300~ ~(50\%)~
• Subtask 2: Không có ràng buộc gì thêm ~(50%)~

Ràng buộc

• ~1 <= N <= 1000~
• ~1 <= sx, sy, gx, gy <= N~
• ~(sx, sy)~ và ~(gx, gy)~ ban đầu là ô trống
• ~1 <= Q <= 10^6~
• ~1 <= ai, bi <= 10^9~

Sample Input

4
1 1 4 1
....
###.
###.
....
3
13 213883
1315 3281
1 1

Sample Output

641662
11158
4

Vương quốc ~Ams~ gồm ~n~ thành phố được liên kết với nhau bằng ~m~ con đường hai chiều, đảm bảo rằng mọi cặp thành phố đều có đường đi trực tiếp hoặc gián tiếp tới nhau. Con đường thứ ~i~ kết nối hai thành phố ~u_i,v_i~, và sẽ tốn ~w_i~ lít xăng để đi qua.

Là một người đam mê du lịch, bạn lên kế hoạch cho chuyến đi chơi của mình tới ~Ams~. Bạn xuất phát từ thành phố ~st~ và có dự định đi tới thành phố ~en~ bằng xe của mình. Tất nhiên đi xe thì phải tốt nhiên liệu, và xe của bạn có một bình xăng chứa được tối đa ~t~ lít xăng.

~Ams~ có ~s~ trạm xăng. Trạm xăng thứ ~i~ được phân bố ở thành phố ~p_i~ và có chi phí cho mỗi lít xăng là ~c_i~. Ở mỗi trạm xăng, bạn có thể mua không giới hạn số xăng (tất nhiên xe bạn chỉ mang tối đa được ~t~ lít xăng thôi).

Bạn bắt đầu từ thành phố ~st~ và xe bạn ban đầu không có xăng - may mắn rằng đảm bảo luôn có trạm xăng ở thành phố nơi bạn xuất phát. Hãy tính số tiền ít nhất cần bỏ ra để hoàn thành hành trình từ ~st~ tới ~en~.

Input

• Dòng đầu gồm ~3~ số nguyên dương ~n,m,s~ ~(2 \le n \le 1000; 1 \le m \le 10^4; 1 \le s \le 100)~
• Dòng tiếp theo gồm một số nguyên dương ~t~ ~(1 \le t \le 10^5)~ mô tả sức chứa của bình xăng.
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm ba số nguyên dương ~u_i,v_i,w_i~ ~(1 \le u_i, v_i \le n; 1 \le w_i \le t)~ miêu tả con đường thứ ~i~.
• ~s~ dòng tiếp theo, dòng thứ ~i~ gồm hai só nguyên dương ~p_i,c_i~ ~(1 \le p_i \le n; 1 \le c_i \le 100)~ miêu tả trạm xăng thứ ~i~.
• Dòng cuối cùng gồm hai số nguyên dương ~st,en~ ~(1 \le st, en \le n)~ miêu tả vị trí ban đầu và đích đến của bạn.

Output

• In ra số tiền ít nhất cần để di chuyển.

Subtask

• Subtask ~1~ ~(30\%)~: ~n \le 100; m \le 100; t \le 500~
• Subtask ~2~ ~(30\%)~: ~t \le 500~
• Subtask ~3~ ~(40\%)~: Không giới hạn gì thêm.

Sample Input 1:

3 3 2
200
1 3 80
1 2 50
2 3 50
1 70
2 40
1 3

Sample Output 1:

5500

Sample Input 2:

5 5 3
100
1 2 80
2 5 80
1 3 40
3 4 60
4 5 60
1 8
2 9
3 2
1 5

Sample Output 2:

1340

Sample Input 3:

4 3 3
10
1 2 2
2 3 6
3 4 3
1 4
2 7
3 9
2 4

Sample Output 3:

61