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