Tý cần giải bài toán sau:

Teo dang choi mot tro choi tinh toan. Tro choi gom \(N\) vong. Vong thu \(i\) co ba thong so \(a_i, b_i, c_i\). De hoan thanh vong \(i\), Teo phai chon mot vong \(j\) truoc do (\(j < i\)) lam moc, sau do mat chi phi:

\[dp_i = c_i + \min_{j < i} (dp_j + a_j \times b_i)\]

Hay tinh chi phi toi thieu de Teo hoan thanh tat ca \(N\) vong.

Dinh dang dau vao

• Dong dau tien chua so nguyen \(N\) (\(1 \le N \le 10^5\)).
• \(N\) dong tiep theo, dong thu \(i\) chua ba so nguyen \(a_i, b_i, c_i\) (\(|a_i|, |b_i|, |c_i| \le 10^9\)).

Dinh dang dau ra

• Mot so nguyen duy nhat la gia tri \(dp_N\).

Vi du

Input:

4
2 1 5
1 3 2
0 2 4
3 4 1

Output:

14

Giai thich: \(dp_1 = 5\), \(dp_2 = 2 + 2 \times 3 + 5 = 13\), \(dp_3 = 4 + \min(5 + 2\times 2, 13 + 1\times 2) = 4 + \min(9, 15) = 13\), \(dp_4 = 1 + \min(5 + 2\times 4, 13 + 1\times 4, 13 + 0\times 4) = 1 + \min(13, 17, 13) = 14\).

Rang buoc

• Subtask 1 (20%): \(N \le 200\).
• Subtask 2 (30%): \(N \le 5000\).
• Subtask 3 (25%): \(N \le 10^5\), \(a_i\) giam dan.
• Subtask 4 (25%): \(N \le 10^5\), khong co rang buoc phu.