Bạn hiện tại đang có số tiền khởi đầu là ~C~ và đang muốn sử dụng máy in tiền để làm giàu như một vì tinh tú nào đó.

Mỗi ngày được chia ra làm ba buổi với ba công việc khác nhau:

• Buổi sáng: Bán máy in tiền mà bạn đã mua trước đó.

• Buổi chiều: Sử dụng máy in tiền để làm giàu.

• Buổi tối: Mua một máy in tiền khác.

Bạn chỉ được phép có duy nhất một máy in tiền; bạn phải bán máy in tiền cũ trước khi được phép mua cái mới.

Bạn đã có thông tin về ~N~ cái máy in tiền. Máy thứ ~i~ chỉ được bán vào ngày thứ ~D_i~ với giá tiền ~P_i~ và sẽ nhận được giá tiền ~R_i~ sau khi bán máy. Máy này có thể in được ~G_i~ giá trị tiền mỗi ngày.

Hãy tính số tiền nhiều nhất bạn có thể có được khi thực hiện sau ~D~ ngày.

Input

Dòng đầu tiên gồm ba số nguyên dương ~N~, ~C~ và ~D~ (~N \leq 10^5~; ~C, D \leq 10^9~) — lần lượt là số thông tin về máy in tiền, giá tiền khởi điểm và số ngày thực hiện.

Trong ~N~ dòng tiếp theo, dòng thứ ~i~ mô tả thông tin về máy in tiền thứ ~i~. Mỗi dòng gồm bốn số nguyên dương ~D_i~, ~P_i~, ~R_i~ và ~G_i~ (~D_i < D~; ~R_i < P_i \leq 10^9~; ~G_i \leq 10^9~) — lần lượt là ngày máy được bán, giá tiền cần có để mua được máy, giá tiền nhận được sau khi bán máy và giá trị tiền mà máy in được mỗi ngày.

Output

Gồm một dòng duy nhất, là số tiền nhiều nhất có được khi thực hiện sau ~D~ ngày.

Sample Input 1

6 10 20
6 12 1 3
1 9 1 2
3 2 1 2
8 20 5 4
4 11 7 4
2 10 9 1

Sample Output 1

44