Một công ty đang thử nghiệm công nghệ sản xuất phản vật chất để dùng làm nhiên liệu cho tàu vũ trụ liên hành tinh. Phản vật chất được tạo ra thông qua các thí nghiệm đặc biệt trong một lò phản ứng.

Có $n$ loại thí nghiệm được biết là có thể tạo ra phản vật chất. Khi thực hiện thí nghiệm loại $i$, một lượng từ $l_i$ đến $r_i$ gam phản vật chất được thêm vào bình chứa đầu ra của lò phản ứng. Vì lý do an toàn, không được tích lũy quá $a$ gam phản vật chất trong bình chứa.

Chi phí thực hiện thí nghiệm loại $i$ là $c_i$, còn giá trị của một gam phản vật chất thu được là $10^9$.

Nếu sau các thí nghiệm, bình chứa có $t$ gam phản vật chất và tổng chi phí thực hiện các thí nghiệm trong lò phản ứng là $s$, thì lợi nhuận được tính bằng công thức $(t\cdot10^9-s)$. Công ty cần xây dựng một chiến lược thực hiện thí nghiệm nhằm tối đa hóa lợi nhuận có thể bảo đảm thu được.

Tùy theo kết quả của những thí nghiệm trước đó, chiến lược xác định loại thí nghiệm cần thực hiện tiếp theo, hoặc quyết định dừng thực hiện thí nghiệm. Một chiến lược bảo đảm thu được lợi nhuận $x$ nếu, với mọi kết quả có thể xảy ra của các thí nghiệm, thứ nhất, bình chứa của lò phản ứng chứa không quá $a$ gam phản vật chất; thứ hai, lợi nhuận không nhỏ hơn $x$.

Ví dụ, giả sử chỉ có một loại thí nghiệm, tạo ra từ $4$ đến $6$ gam phản vật chất, chi phí thực hiện là $10$, và sức chứa của bình là $17$ gam. Khi đó, sau hai lần thực hiện thí nghiệm, bình có thể chứa từ $8$ đến $12$ gam phản vật chất. Nếu thu được $12$ gam thì không thể tiếp tục thí nghiệm nữa, vì nếu thu thêm $6$ gam phản vật chất, bình có thể bị tràn. Trong các trường hợp còn lại, có thể thực hiện thí nghiệm lần thứ ba và thu được từ $12$ đến $17$ gam phản vật chất. Trong trường hợp xấu nhất, phải thực hiện thí nghiệm ba lần với tổng chi phí $30$, và lợi nhuận là $(12\cdot10^9-30)=11\,999\,999\,970$.

Hãy viết chương trình xác định lợi nhuận tối đa $x$ có thể bảo đảm thu được.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên: $n$ là số loại thí nghiệm và $a$ là lượng phản vật chất tối đa được phép có trong bình chứa ($1\le n\le100$, $1\le a\le2\,000\,000$).

Mỗi dòng trong $n$ dòng tiếp theo chứa ba số nguyên $l_i$, $r_i$ và $c_i$, lần lượt là lượng phản vật chất tối thiểu và tối đa thu được khi thực hiện thí nghiệm loại $i$, và chi phí thực hiện thí nghiệm loại đó ($1\le l_i\le r_i\le a$, $1\le c_i\le100$).

Dữ liệu ra

Dữ liệu ra phải chứa một số nguyên: lợi nhuận tối đa $x$ có thể bảo đảm thu được.

Ví dụ

Dữ liệu vào 1

1 17
4 6 10

Dữ liệu ra 1

11999999970

Dữ liệu vào 2

2 11
2 2 100
3 5 5

Dữ liệu ra 2

9999999890

Nhiệm vụ con