Nhận thấy thị trường mua bán dế mèn đang nhộn nhịp, nhiều người đã đổi đời nhờ việc nuôi và mua bán dế, Tahp quyết định dấn thân vào để kiếm lời.

Tahp đã đầu tư một chuồng dế với sức chứa ~l~ con và muốn dùng nó để giàu lên. Tahp dự định sẽ đầu tư trong ~n~ ngày. Ban đầu Tahp không nuôi con dế nào, và đến cuối ngày ~n~ Tahp cũng muốn mình không còn nuôi bất kì con dế nào để tập trung đầu tư vào lĩnh vực khác. Trong ~n~ ngày tiếp theo, Tahp sẽ ra chợ để giao dịch dế.

Vào ngày thứ ~i~, ở chợ có sẵn ~a_i~ con dế được bày bán với giá ~s_i~ đồng mỗi con. Đồng thời, chợ cũng thu mua dế với giá ~b_i~ đồng mỗi con và chỉ thu mua tối đa ~c_i~ con. Tahp có thể chọn mua thêm hoặc bán bớt dế đang nuôi, hoặc không làm gì cả. Tuy nhiên, cuối mỗi ngày, với mỗi con dế đang nuôi, Tahp cần tốn thêm ~k~ đồng để mua thức ăn cho nó. Ngoài ra, với tất cả các ngày, ~b_i \le s_i~.

Giả sử Tahp luôn có đủ tiền để mua thêm dế và mua thức ăn, hãy giúp Tahp tính toán lợi nhuận tối đa có thể sau ~n~ ngày.

Input

Mỗi test có thể chứa nhiều bộ dữ liệu. Dòng đầu tiên chứa số nguyên ~t~ (~1 \le t \le 100~) — số bộ dữ liệu, theo sau đó là ~t~ nhóm dòng có cấu trúc như nhau:

• Dòng đầu tiên chứa ba số nguyên ~n~, ~l~, ~k~ (~1 \le n \le 10^5~, ~1 \le l \le 10^{12}~, ~1 \le k \le 2 \cdot 10^6~) — lần lượt là số ngày Tahp muốn đầu tư, sức chứa của lồng dế và tiền mua thức ăn hàng ngày cho mỗi con dế;

• Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa ba số nguyên ~a_i~, ~s_i~, ~c_i~, ~b_i~ (~1 \le a_i, s_i, c_i, b_i \le 2 \cdot 10^6~; ~b_i \le s_i~) — lần lượt là số lượng dế được bày bán, giá bán ra mỗi con dế, giới hạn số lượng dế thu mua và giá mua vào mỗi con dế ở chợ vào ngày thứ ~i~.

Hai số liên tiếp trên một dòng cách nhau bởi dấu cách. Dữ liệu đảm bảo tổng ~n~ trong tất cả các bộ dữ liệu không vượt quá ~5 \cdot 10^5~.

Output

Với mỗi bộ dữ liệu, in ra tổng lợi nhuận lớn nhất trên một dòng.

Scoring

• Subtask 1 (~750~ điểm): ~l \le 10~.

• Subtask 2 (~1500~ điểm): ~l = 10^{12}~.

• Subtask 3 (~750~ điểm): không có giới hạn gì thêm.

Tổng số điểm nhận được nếu bạn giải thành công bài toán này là ~3000~ điểm.

Sample Input 1

2
3 4 1
2 4 2 1
3 5 1 4
1 10 3 9
2 7 2
8 7 10 1
3 9 3 8

Sample Output 1

9
0

Notes

Ở bộ dữ liệu đầu tiên, Tahp đầu tư trong ~n = 3~ ngày, chuồng dế có sức chứa ~l = 4~ con và tiền mua thức ăn hàng ngày cho mỗi con dế là ~k = 1~ đồng. Một cách để đạt lợi nhuận tối đa là:

• Ở ngày thứ nhất, chợ có ~a_1 = 2~ con dế được bày bán với giá ~s_1 = 4~ đồng mỗi con, và thu mua tối đa ~c_1 = 2~ con dế với giá ~b_1 = 1~ đồng mỗi con. Tahp mua thêm ~2~ con dế với giá ~2 \times 4 = 8~ đồng. Cuối ngày, Tahp đang nuôi tổng cộng ~2~ con dế và cần mua thức ăn hết ~2 \times 1 = 2~ đồng.

• Ở ngày thứ hai, chợ có ~a_2 = 3~ con dế được bày bán với giá ~s_2 = 5~ đồng mỗi con, và thu mua tối đa ~c_2 = 1~ con dế với giá ~b_2 = 4~ đồng mỗi con. Tahp mua thêm ~1~ con dế nữa với giá ~1 \times 5 = 5~ đồng. Cuối ngày, Tahp đang nuôi tổng cộng ~3~ con dế và cần mua thức ăn hết ~3 \times 1 = 3~ đồng.

• Ở ngày thứ ba, chợ có ~a_3 = 1~ con dế được bày bán với giá ~s_2 = 10~ đồng mỗi con, và thu mua tối đa ~c_3 = 3~ con dế với giá ~b_3 = 9~ đồng mỗi con. Tahp bán đi ~3~ con dế đang nuôi với giá ~3 \times 9 = 27~ đồng. Cuối ngày, Tahp đang không nuôi con dế nào nên không phải trả tiền thức ăn.

Tổng lợi nhuận thu được: ~(-8) + (-2) + (-5) + (-3) + 27 = 9~ đồng.