Програмчлалын олимпиадын бодлогын архив

КТМС-ийн төгсөгчид энэ удаагийн хонхны баяраараа бүгд торгон дээл хийж өмсөхөөр шийджээ. Ангийн бүх хүүхдэд дээл хийхэд нийтдээ L метр торго хэрэгтэй. Торгыг N тооны дэлгүүрүүдэд, бөөнөөр авахад хямдралтайгаар зардаг. Дэлгүүр бүрээс зөвхөн бүхэл тоон урттай торго худалдаж авч болно. i-р дэлгүүрийн реклам нь дараах байдлаар бичигдэнэ: “Та манайхаас нэг метр торгыг P_i төгрөгөөр худалдан авч болно. Хэрэв та R_i-гээс багагүй метрийг худалдан авбал метр бүрийн үнэ Q_i төгрөг болно”.

Ангийн дарга нийт үнийг бага байлгахын тулд хэрэгцээнээсээ илүү метр торго авсан ч яах вэ гэж шийджээ. Ингээд дэлгүүрүүд рүү утасдсаны дараа i-р дэлгүүрт дээд тал нь F_i метр торго байгааг олж мэдсэн байна. Түүнд нийт үнэ хамгийн бага байхаар дэлгүүр бүрээс хэдэн метр торго авахыг тооцоолох програм бичиж өгнө үү.

Input

Оролтын файлын эхний мөрөнд N болон L бүхэл тоонууд байрлана (1 ≤ N ≤ 100, 0 ≤ L ≤ 100). Дараагийн N тооны мөр бүрт i-р дэлгүүрийг тодорхойлох P_i, R_i, Q_i болон F_i бүхэл тоонууд өгөгдөнө (1 ≤ Q_i ≤ P_i ≤ 1000, 1 ≤ R_i ≤ 100, 0 ≤ F_i ≤ 100).

Output

Гаралтын файлд шаардлагатай төгрөгийн тоог илэрхийлэх ганц бүхэл тоо байрлана.

Хэрэв дэлгүүрүүдэд байгаа бүх торгоны хэмжээ дээлүүдийг оёход хүрэлцэхгүй бол -1 гэсэн тоог гаргана.

Example

Input:
2 14
7 9 6 10
7 8 6 10

Output:
88
Input:
1 20
1 1 1 1
Output:
-1