Kết thúc buổi thi Olympic Tin học miền Trung-Tây Nguyên, có n thí sinh đang đứng ở một hành lang dài. Nếu coi hành lang là trục Ox thì thí sinh thứ \(i (1≤ i≤ n)\) đứng ở vị trí \(p_i\). Thầy Nhỏ dự định chơi một bản nhạc và muốn thu hút tất cả các thí sinh khác lắng nghe. Thí sinh thứ \(i\) đi một đơn vị độ dài mất \(t_i\ (0< t_i≤ 1000)\) năng lượng và có thể nghe thấy tiếng nhạc nếu đứng ở vị trí cách vị trí thầy Nhỏ không quá \(d_i\). Vì không muốn các thí sinh phải mất thêm nhiều năng lượng sau buổi thi, nên thầy Nhỏ muốn chọn vị trí đứng để chơi nhạc sao cho tổng năng lượng cần di chuyển của tất cả thí sinh là nhỏ nhất.

Yêu cầu: Tính tổng năng lượng ít nhất cần di chuyển của tất cả các thí sinh thỏa mãn yêu cầu của thầy Nhỏ.

Input

• Vào từ thiết bị vào chuẩn có khuôn dạng:
• Dòng đầu chứa số nguyên \(n\);
• Tiếp theo là \(n\) dòng, mỗi dòng chứa ba số nguyên không âm \(p_i,t_i,d_i\).

Output

• Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là tổng năng lượng ít nhất tính được.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n,p_i,d_i≤ 2000\);
• Subtask \(2\) (\(50\%\) số điểm):\(n≤ 10^6,p_i≤ 10^6\) và \(d_i≤ 10^6\);
• Subtask \(3\) (\(25\%\) số điểm): \(n≤ 10^6,p_i≤ 10^9\) và \(d_i≤ 10^9\).

Example

2
0 5 0
7 1 1 

6