Output:

• Dòng 1: Ghi số nguyên s là số lượng các phần tử của dãy con tìm được
• Dòng 2: Ghi s số nguyên là các phần tử trong dãy con tìm được.

Example

Input:

10
10 100 20 1 2 50 70 80 3 60

Output:

5
1 2 50 70 80

Cho một dãy các số nguyên A có N phần tử, hãy tìm đoạn con gồm các phần tử liên tiếp có tổng lớn nhất của dãy A này.

Input:

• Dòng đầu chứa số N.
• Dòng thứ 2 chứa N số, là miêu tả dãy A.

Output:

• Tổng của đoạn con có tổng lớn nhất tìm được.

Example:

Input

6
1 2 3 -1 -1 -1

Output

6

Constraint:

~0 < N \le 10^5; |A_i| \le 10^9~

Cho một dãy số nguyên dương ~a_1, a_2,... a_N, 0 \le a_i \le 32000~. Hãy tỉa bớt một số ít nhất các phần tử của dãy số nguyên đó và giữ nguyên thứ tự các phần tử còn lại sao cho dãy số còn lại là một dãy chỉ bao gồm các số nguyên tố tăng dần. Ta gọi dãy số nguyên tố tăng dần còn lại sau khi đã tỉa bớt một số phần tử là dãy con của dãy đã cho.

Input:

- Dòng đầu ghi số N là số phần tử (1 ≤ N ≤ 10000)
- Dòng tiếp theo ghi N số là các số nguyên của dãy.

Output:

- Dòng 1: Ghi số nguyên số lượng phần tử của dãy con cực đại.
- Dòng 2: Ghi các phần tử trong dãy con đó (theo thứ tự tăng dần), mỗi phần tử cách nhau ít nhất 1 dấu cách.

Example

Input:

10
2 100 3 1 2 50 7 80 13 60

Output:

4
2 3 7 13

Cho n viên đá, viên đá thứ i có độ cao là ~h_i~. Con ếch đang đứng tại viên đá thứ nhất. Tại vị trí thứ i con ếch có thể nhảy sang hòn đá thứ i + 1 hoặc hòn đá thứ i + 2 với chi phí nhảy là |~h_i - h_j~| với j là vị trí đáp của chú ếch.

Yêu cầu: Hãy tìm chi phí ngắn nhất để chú ếch tới được hòn đá thứ n.

Input

• Dòng đầu gồm n là số lượng hòn đá ~(1 \le n \le 10^5)~
• Dòng sau gồm n số, số thứ i thể hiện hi là chiều cao của viên đá thứ i ~(1 \le h_i \le 10^4)~

Output

• Gồm một dòng duy nhất là đáp án cần tìm

Examples

Input

4
10 30 40 20

Output

30

Input

2
10 10

Output

0

Cho n viên đá, viên đá thứ i có độ cao là ~h_i~. Con ếch đang đứng tại viên đá thứ nhất. Tại vị trí thứ i con ếch có thể nhảy sang 1 trong k hòn đá thứ i + 1, i + 2,...,i + k với chi phí nhảy là ~|h_i - h_j|~ với j là vị trí đáp của chú ếch.

Yêu cầu: Hãy tìm chi phí ngắn nhất để chú ếch tới được hòn đá thứ n.

Input

• Dòng đầu gồm n là số lượng hòn đá và số k ~(1 \le n \le 10^5, 1 \le k \le 100)~
• Dòng sau gồm n số, số thứ i thể hiện hi là chiều cao của viên đá thứ i ~(1 \le hi \le 10^4)~

Output

• Gồm một dòng duy nhất là đáp án cần tìm

Examples

Input

5 3
10 30 40 50 20

Output

30

Input

3 1
10 20 10

Output

20

Note

Ở ví dụ 1 chú ếch sẽ nhảy 1 -> 2 -> 5 với chi phí là |10 - 30| + |30 - 20| = 30

Nhân dịp kỷ niệm ngày thành lập Đoàn thanh niên cộng sản Hồ Chí Minh, lớp bạn Tèo có tổ chức đi cắm trại ở khu du lịch sinh thái. Lớp của Tèo có N bạn, trong đó bạn thứ i được đánh giá có độ vui vẻ là 1 số nguyên ~a_i~. Để thuận tiện cho việc quản lý và phân công nhiệm vụ, cô giáo yêu cầu bạn Tèo chọn ra 1 nhóm bạn trong lớp có tổng độ vui vẻ là K.

Yêu cầu: Hãy giúp bạn Tèo tính xem có bao nhiêu cách chọn từ trong lớp một nhóm bạn có tổng độ vui vẻ đúng bằng K theo yêu cầu của cô giáo.

Lưu ý: Mỗi người cũng được xem như 1 nhóm bạn.

Input:

• Dòng đầu tiên: chứa 2 số nguyên N, K được ghi cách nhau 1 ký tự trắng.~( 1\le N \le 25, -10^5 \le K \le 10^5)~
• Dòng tiếp theo chứa N số nguyên ~a_i~ là độ vui vẻ của bạn thứ i ~(1 \le i \le N)~; các số lần lượt ghi cách nhau 1 ký tự trắng. ~(-10^4 \le a_i \le 10^4)~

Output:

• Ghi ra một số nguyên duy nhất là số cách chọn một nhóm bạn có tổng độ vui vẻ bằng k.

Example:

Input:

5  4 
2 3 2 4 2

Output:

4

Sau khi xem rất nhiều trận thi đấu của đội tuyển Việt Nam, người ta thống kê và nhận ra một điều rằng nếu đội hình ra quân có nhiều nhóm cầu thủ hoàn hảo thì khả năng chiến thắng của đội tuyển Việt Nam là càng cao. Một nhóm cầu thủ được gọi là hoàn hảo khi có ít nhất 2 cầu thủ và tổng độ tuổi các cầu thủ chia hết cho số lượng cầu thủ trong nhóm. Bạn hãy giúp huấn luyện viên tính xem có thể lập được bao nhiêu nhóm hoàn hảo trong đội hình ra sân hôm nay. Cho biết đội hình ra sân có N cầu thủ và độ tuổi các cầu thủ đó.

Yêu cầu: Tính số nhóm hoàn hảo có thể có trong đội hình.

Input:

• Dòng 1: Ghi số nguyên dương N là số cầu thủ trong đội hình ~(2 \le N \le 20)~.

• Dòng 2. Ghi N số nguyên dương ~A_1, A_2,.....,A_N~, với ~A_i~ là số tuổi của cầu thủ thứ i.

  Output:

• Dòng 1: Ghi 1 số nguyên dương là số lượng nhóm hoàn hảo tìm được.

Example:

Input:

3
3 7 5

Output:

4

Input:

3
1 6 2

Output:

2

Có N người sắp hàng mua vé dự buổi hoà nhạc. Ta đánh số họ từ 1 đến N theo thứ tự đứng trong hàng. Mỗi người cần mua một vé, song người bán vé được phép bán cho mỗi người tối đa hai vé. Vì thế, một số người có thể rời hàng và nhờ người đứng trước mình mua hộ vé. Biết ti là thời gian cần thiết để người i mua xong vé cho mình. Nếu người i + 1 rời khỏi hàng và nhờ người i mua hộ vé thì thời gian để người thứ i mua được vé cho cả hai người là ri.

Yêu cầu: Xác định xem những người nào cần rời khỏi hàng và nhờ người đứng trước mua hộ vé để tổng thời gian phục vụ bán vé là nhỏ nhất.

Input

• Dòng đầu tiên chứa số N ~(1 \le N \le 10^5)~.
• Dòng thứ 2 ghi N số nguyên dương t1, t2, ..., tN. ~(1 \le t_i \le 30000)~
• Dòng thứ ba ghi N - 1 số nguyên dương ~r_1, r_2, ..., r_{N - 1}. (1 \le r_i \le 30000)~

Output

• Gồm một dòng duy nhất là đáp án cần tìm

Examples

Input

5
2 5 7 8 4
4 9 10 10

Output

18

Input

4
5 7 8 4
50 50 50

Output

24

Bờm chơi trò chơi điện tử Lucky Luke đến màn phải điều khiển Lucky leo lên một cầu thang gồm n bậc. Các bậc thang được đánh số từ 1 đến n từ dưới lên trên. Lucky có thể đi lên một bậc thang, hoặc nhảy một bước lên hai bậc thang. Tuy nhiên một số bậc thang đã bị thủng do cũ kỹ và Lucky không thể bước chân lên được. Biết ban đầu, Lucky đứng ở bậc thang số 1 (bậc thang số 1 không bao giờ bị thủng). Chơi đến đây, Bờm chợt nảy ra câu hỏi: có bao nhiêu cách để Lucky leo hết được cầu thang? (nghĩa là leo đến bậc thang thứ n). Bờm muốn nhờ bạn trả lời câu hỏi này.

Input

• Dòng đầu tiên: gồm 2 số nguyên n và k, là số bậc của cầu thang và số bậc thang bị hỏng ~(0 \le k < n \le 10^5)~.
• Dòng thứ hai: gồm k số nguyên cho biết chỉ số của các bậc thang bị hỏng theo thứ tự tăng dần.

Output

• In ra phần dư của số cách Lucky leo hết cầu thang khi chia cho 14062008

Examples

Input

4 2
2 3

Output

0

Input

90000 1
49000

Output

4108266

Minh là một học sinh rất yêu thích lập trình, em đã tạo ra một Game X nhằm giúp người chơi phát triển tư duy toán học. Game được mô tả như sau: cho trước n tấm thẻ hình chữ nhật được đánh số thứ từ 1 đến n, tấm thẻ thứ i ghi một số nguyên dương n. Mỗi lượt chơi, người chơi cần chọn số lượng tấm thẻ nhiều nhất có thể và tuân thủ các quy tắc của trò chơi như sau: Chọn ra một số tấm thẻ xếp thành hàng ngang, sao cho thứ tự tấm thẻ tăng dần theo chỉ số từ trái sang phải. Tấm thẻ i, j ~(1 \le i, j \le n)~ xếp cạnh nhau cần thỏa các điều kiện:

• ~0 < |i - j| \le 10~

• ~|a_j - a_i| > 0~

• ~|a_j - a_i|~ là bình phương của một số tự nhiên

Yêu cầu: Cho biết số lượng tấm thẻ nhiều nhất mà người chơi có thể chọn được trong mỗi lượt chơi

Input

• Dòng thứ nhất gồm n ~(1 \le n \le 10^5)~
• Dòng thứ i trong n dòng tiếp theo chứa số nguyên dương ai ~(1 \le a_i \le 10^9)~

Output

• Gồm một dòng duy nhất là đáp án cần tìm

  Example

Input

7
2
6
2
31
22
11
26

Output

5

Note

• Dãy dài nhất có 5 phần tử là: 2, 6, 31, 22, 26

Nhà trường có một phòng hội trường. Có những yêu cầu muốn sử dụng phòng hội trường này, mỗi yêu cầu cho biết thời điểm bắt đầu và thời điểm kết thúc. Nhà trường có thể chấp nhận hoặc từ chối đối với một yêu cầu.

Yêu cầu: hãy giúp nhà trường chọn các yêu cầu sử dụng hội trường sao cho tổng thời gian hội trường được sử dụng là lớn nhất.

Input:

• Dòng đầu tiên chứa một số nguyên dương ~N(N \le 10000)~ số yêu cầu.

• Mỗi dòng trong số N dòng tiếp theo chứa 2 số nguyên dương p và k ~(0 \le p < k \le 30000)~, mô tả một yêu cầu bắt đầu tại thời điểm p và kết thúc tại thời điểm k.

Output:

• Gồm một dòng duy nhất là tổng thời gian lớn nhất mà hội trường được sử dụng

Example:

Input:

12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20

Output:

16

Trung tâm tính toán hiệu năng cao nhận được đơn đặt hàng của n khách hàng. Khách hàng i muốn sử dụng máy trong khoảng thời gian từ ~a_i~ đến ~b_i~ và trả tiền thuê là ~c_i~.

Yêu cầu: Hãy bố trí lịch thuê máy để tổng số tiền thu được là lớn nhất mà thời gian sử dụng máy của 2 khách hàng bất kì được phục vụ đều không giao nhau (cả trung tâm chỉ có một máy cho thuê).

Input

• Dòng đầu tiên chứa một số nguyên dương n (~n \le 10^4~)
• Mỗi dòng trong số n dòng tiếp theo, dòng thứ i chứa 3 số nguyên dương ~a_i, b_i, c_i (0 \le a_i < b_i \le 10^5, 1 \le c_i \le 10^5)~

  Output

Gồm một dòng duy nhất là tổng số tiền thu được lớn nhất

Examples

Input

3
4 11 10
1 5 4
5 10 5

Output

10

Input

4
4 11 1
1 5 1
5 10 1
1 100 1

Output

2

Dãy số nguyên ~a_1, a_2,…,a_n~ được gọi là dãy lõm nếu nó tăng dần từ ~a_1~ tới ~a_i~ nào đó, rồi giảm dần tới ~a_n~.

Ví dụ: dãy 2 4 5 4 3 1 là dãy lõm.

W là 1 dãy các số nguyên dương. Nó có các đặc điểm sau:

• Độ dài của dãy là 1 số lẻ: ~L = 2 * N + 1~

• ~N + 1~ số nguyên đầu tiên của dãy tạo thành 1 dãy tăng

• ~N + 1~ số nguyên cuối của dãy tạo thành 1 dãy giảm

• Không có 2 số nguyên nào cạnh nhau trong dãy có giá trị bằng nhau

Ví dụ: 1, 2, 3, 4, 5, 4, 3, 2, 1 là 1 dãy W độ dài 9. Tuy nhiên, dãy 1, 2, 3, 4, 5, 4, 3, 2, 2 không là 1 dãy W

Yêu cầu: Trong các dãy con của dãy số cho trước, tìm dãy W có độ dài dài nhất.

Input

• Dòng 1: số nguyên dương ~N(N \le 10^3)~, độ dài dãy số.
• Dòng 2: N số nguyên dương ~a_i (a_i ≤ 10^9)~.

Output

• Ghi 1 số nguyên dương duy nhất là độ dài dãy W dài nhất.

Examples

Input

10
1 2 3 4 5 4 3 2 1 10

Output

9

Input

19
1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1

Output

9

Người ta định nghĩa: Một xâu được gọi là xâu đối xứng (palindrome) nếu như xâu đó đọc từ trái sang phải hay đọc từ phải sang trái đều như nhau. Cho một xâu ~S~, người ta định nghĩa một xâu con của ~S~ là xâu thu được khi xóa đi một số kí tự từ xâu ~S~ ban đầu.

Yêu cầu: Hãy tìm số kí tự ít nhất cần xoá để xâu con của ~S~ là xâu đối xứng ?

Input

• Dòng 1: Chứa xâu ~S~ chỉ gồm các chữ cái in thường, giới hạn độ dài không quá ~2000~.

Output

• Dòng 1: Ghi ra số lượng ký tự cần xoá ít nhất để thu được xâu con đối xứng trích từ xâu S.

Example

Input:

lmevxeyzl

Output:

4

P/S:

Vì chưa rõ ý đồ giới hạn của tác giả nên test chấm chỉ mang tính chất tham khảo, test đang rất yếu.**

Do diễn biến phức tạp của dịch bệnh Covid-19 nên các cơ sở y tế đã mở dịch vụ tiêm vaccine cho các doanh nghiệp, cơ quan và các tổ chức xã hội (tạm gọi là các đơn vị). Vì bận công việc nên các đơn vị đưa ra yêu cầu về thời gian tiêm chủng để các cơ sở y tế sắp xếp lịch tiêm. Giả sử có N đơn vị cần tiêm được đánh số từ 1 đến N. Đơn vị thứ i tiêm bắt đầu từ thời điểm ~d_i~ đến thời điểm ~c_i (d_i, c_i~ là các số nguyên và ~0 < d_i < c_i < 10^6)~ và sẽ trả số tiền là ~p_i (p_i nguyên, 0 < p_i \le 10^6)~.

Yêu cầu: Giả sử em đóng vai trò là một nhân viên y tế của cơ sở đó, hãy đưa ra những lựa chọn xem cần nhận phục vụ những đơn vị nào sao cho khoảng thời gian thời gian tiêm của hai đơn vị được nhận phục vụ bất kỳ không được giao nhau đồng thời và tổng tiền thu được từ việc phục vụ họ là lớn nhất.

Input:

• Dòng 1: Ghi số nguyên dương ~N (0 < N \le 10^4)~;
• Dòng thứ i+1 trong số N dòng tiếp theo ghi 3 số di, ci,pi cách nhau bởi dấu trắng ~(i = 1, 2,...n)~.

Output

• Dòng 1. Ghi số nguyên dương T là tổng tiền thu được từ việc phục vụ các đơn vị.
• Dòng 2. Ghi chỉ số của các đơn vị được nhận phục vụ.

Example

Input1

3
150 500 150
1 200 100
400 800 80

Output1

180
2 3

Input2

4
400 821 800
200 513 500
100 325 200
600 900 600

Giải thích

• Đơn vị thứ 2 và 3 được nhận phục vụ với tổng tiền là 180

Output2

1100
2 4

Giải thích

• Đơn vị thứ 2 và 4 được nhận phục vụ với tổng tiền là 1100

Các học sinh khi đến thực tập trong phòng máy tính thường hay chơi trò chơi điện tử trên mạng. Để ngăn ngừa, người trực phòng máy đã ngắt tất cả các máy tính ra khỏi mạng và xếp chúng thành một dãy trên một cái bàn dài và gắn chặt máy xuống mặt bàn rồi đánh số thứ tự các máy từ 1 đến N theo chiều từ trái sang phải.

Các học sinh tinh nghịch không chịu thua, họ đã quyết định tìm cách nối các máy trên bàn bởi các đoạn dây nối sao cho mỗi máy được nối với ít nhất một máy khác. Để tiến hành công việc này, họ đã đo khoảng cách giữa hai máy liên tiếp. Bạn hãy giúp các học sinh này tìm cách nối mạng thoả mãn yêu cầu đặt ra sao cho tổng độ dài cáp nối phải sử dụng là ít nhất.

Input

• Dòng đầu tiên chứa số lượng máy N ~(2 \le N \le 10^5)~.
• Dòng thứ i trong số N - 1 dòng tiếp theo chứa các khoảng cách từ máy i đến máy i + 1 (i = 1, 2, ..., N - 1). Giả thiết rằng khoảng cách từ máy 1 đến máy N không vượt quá ~10^6~.

Output

• Gồm một dòng duy nhất là đáp án cần tìm

Example

Input

6
2
2
3
2
2

Output

7

Note

• Nối máy 1 -> 2, 3 -> 4, 5 -> 6

• Tổng là 2 + 3 + 2 = 7

There are N items, numbered ~1, 2,..., N~. For each ~i~ ~(1 ≤ i ≤ N)~, Item ~i~ has a weight of ~w_i~ and a value of ~v_i~ Taro has decided to choose some of the ~N~ items and carry them home in a knapsack. The capacity of the knapsack is ~W~, which means that the sum of the weights of items taken must be at most ~W~. Find the maximum possible sum of the values of items that Taro takes home.

Constraints

• All values in input are integers.

• ~1 ≤ N ≤ 100~

• ~1 ≤ W ≤ 10^9~

• ~1≤ w_i≤W~

• ~1 ≤ v_i ≤ 10^3~

Input

• Input is given from Standard Input in the following format:

~N~ ~W~

~w_1~ ~v_I~

~w_2~ ~v_2~

.

.

~w_N~ ~v_N~

Output

• Print the maximum possible sum of the values of items that Taro takes home.

Example 1

Input

3 8
3 30
4 50
5 60

Output

90

Example 2

Input

1 1000000000
1000000000 10

Output

10

Example 3

Input

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Output

17

There are N items, numbered ~1, 2,..., N~. For each ~i~ (~1 ≤ i ≤ N)~, Item ~i~ has a weight of ~w_i~ and a value of ~v_i~ Taro has decided to choose some of the ~N~ items and carry them home in a knapsack. The capacity of the knapsack is ~W~, which means that the sum of the weights of items taken must be at most ~W~. Find the maximum possible sum of the values of items that Taro takes home.

Constraints

• All values in input are integers.

• ~1 ≤ N ≤ 18~

• ~1 ≤ W ≤ 5*10^9~

• ~1≤ w_i≤ 10^9~

• ~1 ≤ v_i ≤ 10^9~

Input

Input is given from Standard Input in the following format:

~N~ ~W~

~w_1 v_I~

~w_2 v_2~

:

~w_N v_N~

Output

Print the maximum possible sum of the values of items that Taro takes home.

Example 1

Input

3 8
3 30
4 50
5 60

Output

90

Example 2

Input

1 1000000000
1000000000 10

Output

10

Example 3

Input

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Output

17

Nhân dịp chào mừng kỷ niệm ngày thành lập Quân đội Nhân dân Việt Nam, Liên đội đã lên kế hoạch tổ chức Hội thi kéo co giữa các lớp trong toàn trường. Theo quy định của Ban tổ chức, số lượng thành viên của mỗi đội thi là không hạn chế và tổng cân nặng của các thành viên tham gia mỗi đội không vượt quá K kilogam. Là lớp trưởng lớp 9A, Tý cũng rất háo hức để chuẩn bị cho đội thi của lớp mình nên đã tìm hiểu rất kỹ về Hội thi. Sau khi tham khảo kinh nghiệm từ các thầy cô, cậu biết được rằng đội nào có tổng chiều cao các thành viên lớn nhất thì thường là đội vô địch. Do đó, Tý cũng rất muốn chọn ra đội thi của lớp mình sao cho tổng chiều cao các thành viên trong đội là lớn nhất.
Lớp của Tý có N học sinh được đánh số từ 1 đến N. Cân nặng tương ứng của các thành viên là ~a_1, a_2, ..., a_N~ và chiều cao tương ứng của các thành viên là ~b_1, b_2, ..., b_N~.

Yêu cầu: Hãy lập trình giúp Tý chọn được các thành viên của đội sao cho tổng chiều cao của đội là lớn nhất mà vẫn đảm bảo quy định của Ban tổ chức.

Dữ liệu vào:

Cho trong tệp văn bản KNAPSACK4.INP có cấu trúc như sau:

• Dòng 1: Ghi 2 số nguyên dương N, K (~1 ≤ N ≤ 150, 1 ≤ K ≤ 10^9~).
• Dòng 2: Ghi N số nguyên dương ~a_1, a_2, ... a_N~. (~1 ≤ i ≤ N, 1 ≤ a_i ≤ 10^9~).
• Dòng 3: Ghi N số nguyên dương ~b_1, b_2, ... b_N~. (~1 ≤ i ≤ N, 1 ≤ b_i ≤ 10^3~). Các số trên cùng một dòng được ghi cách nhau một dấu cách.

Dữ liệu ra:

Ghi ra tệp văn bản KNAPSACK4.OUT theo cấu trúc như sau:

• Dòng 1: Ghi một số nguyên dương t duy nhất là tổng chiều cao lớn nhất có thể của đội thi.

Ví dụ:

Input

5 140 
44 50 30 35 46
130 150 120 150 140

Output

440

Giới hạn:

• Có 70% số test tương ứng với 70% số điểm của câu có (~1 ≤ N ≤ 20, 10^5 ≤ K ≤ 10^9~)
• Có 30% số test tương ứng với 30% số điểm của câu có (~100 < N ≤ 150, 1 ≤ K ≤ 10^4~)

Vườn zayzen123 có một cây khế ngọt, năm lần bảy lượt chim thần cứ đến xin khế, hôm qua chim thần lại đến. Lần này chim thần chở zayzen123 đến đảo đá quý. Trên hòn đảo bây giờ chỉ còn N loại đá quý. Loại thứ i có trọng lượng là ~w_i~ có giá trị là ~v_i~. zayzen123 mang theo túi "mười lăm" gang có thể chứa tối đa trọng lượng là M. Hỏi tổng giá trị tối đa của các viên đá quý mà zayzen123 có thể mang về là bao nhiêu, biết rằng zayzen123 chỉ được phép lấy mỗi loại một viên?

Input:

• Dòng đầu tiên ghi hai số N và M ~(1 ≤ N,M ≤ 1000)~.

• N dòng tiếp theo, dòng thứ i ghi ba số ~w_i , v_i~ lần lượt là trọng lượng, giá trị và số lượng của loại đá quý thứ i ~(0 ≤ w_i, v_i ≤ 10^3)~

Output:

• Ghi ra một số nguyên duy nhất là tổng giá trị lớn nhất mà zayzen123 em có thể mang về.

Example:

input

3 50
10 60
20 100
30 120

output

220

Khác với lần trước, lần này chim thần chở zayzen123 đến một hòn đảo khác với vô số đá quý. Trên hòn đảo bây giờ có N loại đá quý. Loại thứ i có trọng lượng là ~w_i~ có giá trị là ~v_i~ và có số lượng là ~a_i~. Lần này Zayzen123 mang theo túi "năm trăm gang" có thể chứa tối đa trọng lượng là M. Hỏi tổng giá trị tối đa của các viên đá quý mà zayzen123 có thể mang về là bao nhiêu?

Input:

• Dòng đầu tiên ghi hai số N và M ~(1 ≤ N,M ≤ 1000)~.

• N dòng tiếp theo, dòng thứ i ghi ba số ~w_i , v_i , a_i~ lần lượt là trọng lượng, giá trị và số lượng của loại đá quý thứ i ~(0 ≤ w_i, v_i , a_i ≤ 10^3)~

Output:

• Ghi ra một số nguyên duy nhất là tổng giá trị lớn nhất mà zayzen123 em có thể mang về.

Example:

input

3 4 
1 4 2 
2 7 2 
3 6 1   

output

15

Năm lần bảy lượt chim thần đến nhà Zayzen123 để xin khế. Lần này trên cây chỉ còn 1 quả cuối cùng. Zayzen123 muốn giữ lại để chấm muối ớt vì từ đầu mùa đến giờ đã có quả nào bỏ vào bụng đâu. Khóc lóc, van xin một hồi lâu, cuối cùng Zayzen123 cũng xiêu lòng và đem quả khế cuối cùng cho chim thần. Lần này chim thần trả công cho Zayzen123 rất hậu hĩnh, chim thần chở zayzen123 đến một hòn đảo khác với vô số đá quý. Trên hòn đảo bây giờ có N loại đá quý. Loại thứ i có trọng lượng là ~w_i~ có giá trị là ~v_i~ và có số lượng mỗi loại nhiều vô kể. Khác với lần trước, lần này Zayzen123 mang theo túi "năm trăm gang" có thể chứa tối đa trọng lượng là M. Hỏi tổng giá trị tối đa của các viên đá quý mà zayzen123 có thể mang về là bao nhiêu? Biết rằng, zayzen1234 có thể chọn 1 loại đá quý với số lượng tuỳ thích.

Input:

• Dòng đầu tiên ghi hai số N và M ~(1 ≤ N,M ≤ 1000)~.

• N dòng tiếp theo, dòng thứ i ghi hai số ~w_i , v_i~ lần lượt là trọng lượng và giá trị của loại đá quý thứ i ~(0 ≤ w_i, v_i ≤ 10^3)~

Output:

• Ghi ra một số nguyên duy nhất là tổng giá trị lớn nhất mà zayzen123 em có thể mang về.

Example:

input

5 15
12 4
2 2
1 1
1 2
4 10

output

36