Vào dịp Tết Nguyên Đán, một gia đình đang chuẩn bị mâm quà Tết để biếu họ hàng. Gia đình có ~n~ loại quà, mỗi loại quà thứ ~i~ có:

• Trọng lượng ~w_i~
• Giá trị ~v_i~
• Số lượng tối đa ~a_i~

Gia đình này có quan niệm tròn vị ngày Tết rằng:

• Một mâm quà được gọi là tròn vị ngày Tết nếu tổng trọng lượng của mâm quà không vượt quá ~S~ và chia hết cho ~K~.
• Chi phí của một mâm quà bằng tổng giá trị các món quà trong mâm.

Hãy tính tổng chi phí nhỏ nhất của tất cả các mâm quà Tết tròn vị có thể tạo được từ các món quà đã cho. Kết quả lấy modulo ~20268386~.

Đầu vào

• Dòng đầu gồm ~3~ số nguyên dương: ~n~, ~S~, ~K~ ~(1 \leq n \leq 100, 1 \leq K \leq S \leq 100000)~
• ~n~ dòng tiếp theo, mỗi dòng gồm ~3~ số nguyên dương: ~w_i~, ~v_i~, ~a_i~ ~(1 \leq w_i \leq S, 1 \leq v_i \leq 10^9, 1 \leq a_i \leq 1000)~

Đầu ra

In ra một số nguyên duy nhất — tổng chi phí nhỏ nhất của tất cả các mâm quà Tết tròn vị có thể tạo ra, modulo ~20268386~.

Ví dụ

Đầu vào

2 10 2
2 3 3
3 4 2

Đầu ra

42

Giải thích

Giải thích: các mâm quà trọn vị có thể tạo ra là các mâm quà có trọng lượng 2 , 4 ,6 , 8 , 10 với tổng chi phí của từng mâm quà là 3 + 6 + 8 + 11 + 14 = 42.

Ghi chú

• Chỉ những mâm quà có tổng trọng lượng chia hết cho ~K~ mới được coi là tròn vị.
• Nếu một tổng trọng lượng thỏa mãn điều kiện tròn vị nhưng không thể tạo được mâm quà, thì không tính vào kết quả.

Tính điểm

• Subtask ~1~ ~(50~ điểm~)~ : ~1 \leq a_i \leq 2.~
• Subtask ~2~ ~(50~ điểm~)~ : Không có ràng buộc gì thêm.