Farmer John đến thị trấn mua $K$ pound thức ăn ($1 \le K \le 100$). Đi $D$ dặm với $K$ pound trên xe tải tốn $D*K$ cent.

Chợ của hạt có $N$ cửa hàng ($1 \le N \le 100$), đánh số $1..N$, trên đoạn trục $X$ dài $E$ ($1 \le E \le 350$). Cửa hàng $i$ tại $X_{i}$ ($0 < X_{i} < E$) bán tối đa $F_{i}$ pound ($1 \le F_{i} \le 100$), giá $C_{i}$ cent mỗi pound ($1 \le C_{i} \le 1,000,000$). Có thể có nhiều cửa hàng tại cùng điểm trên trục $X$.

FJ bắt đầu ở 0 và chỉ đi hướng dương, cuối cùng đến $E$ với ít nhất $K$ pound. Anh có thể dừng ở cửa hàng bất kỳ trên đường và mua lượng bất kỳ tới hạn mức của cửa hàng.

Chi phí tối thiểu để mua và chở $K$ pound là bao nhiêu? FJ biết có lời giải.

Ví dụ cần hai pound từ ba cửa hàng tại 1, 3, 4 trên trục $0..5$:

      0   1   2   3   4   5
      +---|---+---|---|---+
          1       1   1      Pound thức ăn có sẵn
          1       2   2      Cent mỗi pound

Tốt nhất mua một pound tại mỗi cửa hàng thứ hai và thứ ba, mỗi pound hai cent, tổng 4. Từ 3 đến 4 đi 1 đơn vị với 1 pound, tốn $1*1 = 1$ cent.

Từ 4 đến 5 đi 1 đơn vị với 2 pound, tốn $1*2 = 2$ cent.

Tổng là $4+1+2 = 7$ cent.

Dữ liệu vào

• Dòng 1: ba số nguyên $K$, $E$, $N$ cách nhau bằng khoảng trắng.

• Dòng $2..N+1$: dòng $i+1$ chứa ba số nguyên $X_{i}$, $F_{i}$, $C_{i}$ cách nhau bằng khoảng trắng.

Dữ liệu ra

• Dòng 1: một số nguyên, chi phí tối thiểu để mua và chở thức ăn.

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

7

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