Lan dự định xuất phát từ địa điểm $0$, lần lượt đi qua các địa điểm $1, 2, \ldots, n$, cuối cùng đến địa điểm $n$.

Đi từ địa điểm $i-1$ đến địa điểm $i$ cần tiêu tốn $Dis_i$ lít xăng.

Tại địa điểm $i$ ($1 \le i \le n$) có một trạm xăng, có thể đổ xăng với giá $Cost_i$ cho mỗi lít, đổ tối đa $Lim_i$ lít.

Bình xăng ô tô của Lan có dung tích $m$ lít, ban đầu bình rỗng (nhưng có thể đổ xăng tại điểm xuất phát).

Hãy tìm chi phí nhỏ nhất để đến đích. Nếu không thể đến nơi, in ra $-1$.

Dữ liệu vào

Dòng đầu tiên gồm hai số nguyên $n$ và $m$, biểu thị số địa điểm và dung tích bình xăng.

Tiếp theo là $n$ dòng, mỗi dòng gồm ba số nguyên $Dis_i, Cost_i, Lim_i$.

Dữ liệu ra

In ra một số nguyên, là chi phí nhỏ nhất. Nếu không thể đến nơi, in ra $-1$.

Ví dụ

Input

4 5
2 3 2
3 4 2
4 5 3
2 6 3

Output

38

Ghi chú

Phạm vi dữ liệu

• $1 \le n \le 100$
• $1 \le m \le 200$
• $1 \le Dis_i, Cost_i, Lim_i \le 200$