Sau nhiều năm làm việc vất vả, Nam đã chính thức lên vị trí quản lí. Cụ thể là quản lí các công việc của nhân viên. Hôm nay, Nam nhận được thông tin của ~n~ công việc tương ứng với các mốc thời gian ~1~->~n~, công việc thứ ~i~ được mô tả bởi ~4~ thông tin ~a_i, b_i, t_i, d_i~, mỗi công việc đòi hỏi độ khó cao nên tất cả nhân viên sẽ cùng thực hiện và không thể làm cùng lúc nhiều công việc.

Nhiệm vụ của Nam là chọn ra các công việc sao cho lợi nhuận của công ty là lớn nhất.

• Khi thực hiện công việc thứ ~i~ công ty sẽ nhận được số tiền là ~b_i~ , công việc thứ ~i~ sẽ mất thời gian là ~t_i~ nên khi thực hiện công việc này công ty không thể thực hiện các công việc ~j~ với ~j < i + t_i~.
• Mỗi khi thực hiện công việc ~i~ nhân viên sẽ có độ nhiệt huyết là ~a_i~, giả sử chỉ số của công việc trước đó là ~x~ thì công ty sẽ nhận thêm được số tiền là ~(a_i-a_x)\times d_x~ khi ~a_i > a_x~, ngược lại công ty sẽ bị giảm lợi nhuận

Yêu cầu: Vì đây là ngày đầu tiên làm quản lí Nam còn gặp nhiều khó khăn trong việc tìm ra phương án tối ưu nhất. Hãy giúp Nam chọn ra các công việc sao cho tổng lợi nhuận của công ty là lớn nhất có thể.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(n \le 2 \times10^{5})~
• ~n~ dòng tiếp theo mỗi dòng chứa ~4~ số nguyên dương ~a_i, b_i, t_i, d_i~ ~(a_i, d_i \le 1000, b_i \le 10^{6}, t_i \le 10)~

Dữ liệu ra

• Một dòng duy nhất chứa đáp án của bài toán

Ràng buộc

• Subtask ~1 \ (30\%)~ : ~N \le 20~
• Subtask ~2 \ (25\%)~ : ~N \le 5000~
• Subtask ~3 \ (25\%)~ : ~a_i = 1, \ \forall i \in [1, N]~
• Subtask ~4 \ (10\%)~ : ~t_i = 1, \ \forall i \in [1, N]~
• Subtask ~5 \ (10\%)~ : không có ràng buộc gì thêm

Ví dụ

Dữ liệu vào

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

Dữ liệu ra

11

Giải thích

Phương án tối ưu là chọn công việc ~2, 3~ và ~5~

• Đầu tiên, nhân viên làm công việc ~2~ thu được lợi nhuận là ~6~
• Tiếp theo, nhân viên làm công việc ~3~ thu được lợi nhuận là ~6 + 2 + (2-3)\times2 = 6~
• Cuối cùng, nhân viên làm công việc ~5~ thu được lợi nhuận là ~8 + 1 + (4-2)\times2 = 11~