Đề bài

Có N môn thi, mỗi môn i có thời lượng \(d_i\) , hạn cuối phải thi xong \(t_i\) , và điểm phạt \(p_i\) nếu thi sau hạn (mỗi đơn vị thời gian muộn thêm bị phạt \(p_i\)). Một sinh viên chỉ thi từng môn một, bắt đầu từ thời điểm 0, có thể sắp xếp thứ tự các môn tùy ý. Hãy tìm thứ tự thi sao cho tổng điểm phạt là nhỏ nhất.

Dữ liệu vào

\(N (1 \le N \le 2 * 10^5)\)

Mỗi dòng \(i (1...N)\) : \(d_i , t_i , p_i (1 \le d_i , t_i , p_i \le 10^9)\)

Dữ liệu ra

Một số nguyên: tổng điểm phạt nhỏ nhất.

Ví dụ