사료 구매 II

농부 존(Farmer John, FJ)은 사료 $K$파운드($1 \le K \le 100$)를 사기 위해 마을로 가야 한다. 트럭에 사료 $K$파운드를 싣고 $D$마일을 달리면 운송 비용으로 $D \times K$센트가 든다.

마을의 사료 구역에는 사료를 파는 상점이 $N$개($1 \le N \le 100$, 편의상 $1$번부터 $N$번까지 번호를 매긴다) 있다. 모든 상점은 길이가 $E$($1 \le E \le 350$)인 $X$축 구간 위에 있다. 상점 $i$는 수직선상의 위치 $X_i$($0 < X_i < E$)에 있으며, 파운드당 $C_i$센트($1 \le C_i \le 1{,}000{,}000$)의 가격으로 최대 $F_i$파운드($1 \le F_i \le 100$)까지 사료를 판다. 놀랍게도 같은 위치에 상점이 여러 개 있을 수도 있다.

FJ는 수직선의 위치 $0$에서 출발하여 양의 방향으로만 이동할 수 있으며, 최종적으로 사료를 적어도 $K$파운드 실은 채 위치 $E$에 도착해야 한다. 이동 도중 어떤 상점에서든 멈춰서 그 상점의 판매 한도까지 원하는 만큼 사료를 살 수 있다.

FJ가 사료 $K$파운드를 사서 위치 $E$까지 운반하는 데 드는 최소 비용은 얼마인가? 해가 반드시 존재함이 보장된다.

• 첫째 줄: 공백으로 구분된 세 정수 $K$, $E$, $N$이 주어진다.
• 둘째 줄부터 $N+1$째 줄까지: $i+1$째 줄에는 상점 $i$를 나타내는 세 정수 $X_i$, $F_i$, $C_i$가 공백으로 구분되어 주어진다.

• 첫째 줄: FJ가 사료를 사서 운반하는 데 드는 최소 비용을 나타내는 정수 하나를 출력한다.