Farmer John đến thị trấn mua $K$ ($1 \le K \le 10,000$) pound thức ăn. Một dặm mang $K$ tốn $K*K$ xu, $D$ dặm $D*K*K$.

$N$ ($1 \le N \le 500$) cửa hàng $1..N$ trên trục $X$, đoạn dài $E$ ($1 \le E \le 500$) dặm. Cửa hàng $i$ tại $X_{i}$ ($0 < X_{i} < E$), bán tối đa $F_{i}$ ($1 \le F_{i} \le 10,000$) pound giá $C_{i}$ ($1 \le C_{i} \le 10,000,000$) xu mỗi pound. Nhiều cửa hàng có thể cùng điểm.

Từ 0 chỉ chiều dương, đến $E$ với ít nhất $K$. Dừng bất kỳ cửa hàng, mua lượng tùy ý đến giới hạn.

Tìm chi phí mua và chở $K$ ít nhất. Biết có thể mua đủ.

Hai pound, ba cửa hàng 1,3,4 trên $0..5$:

      0   1   2   3   4   5  X
      +---|---+---|---|---+
          1       1   1      Pound có sẵn
          1       2   2      Xu mỗi pound

Tốt nhất mua mỗi pound ở thứ hai, thứ ba, 2 xu mỗi, tổng mua 4. 0–3 không hàng miễn phí; 3–4 một dặm một pound tốn $1*1*1 = 1$ xu.

4–5 một dặm hai pound tốn $1*2*2 = 4$ xu.

Mua $2+2$, chở $1+4$, tổng $2 + 2 + 1 + 4 = 9$ xu.

Dữ liệu vào

• Dòng 1: nguyên $K$, $E$, $N$ cách dấu cách.
• Dòng $2..N+1$: dòng $i+1$, nguyên $X_{i}$, $F_{i}$, $C_{i}$ cách dấu cách.

Dữ liệu ra

• Dòng 1: nguyên, mua và chở ít nhất.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

9

Tác giả bài toán: Tom Conerly, 2009