사료 구입

농부 존(FJ)은 마을에 가서 사료 $K$($1 \le K \le 10,000$) 파운드를 실어 와야 합니다. 사료 $K$ 파운드를 실은 채 $1$ 마일을 달리면 $K \times K$ 센트가 들고, 같은 짐으로 $D$ 마일을 달리면 $D \times K \times K$ 센트가 듭니다.

FJ는 사료를 파는 상점 $N$($1 \le N \le 500$) 곳 중 어디에서든 살 수 있으며, 상점에는 $1 \ldots N$ 번호가 붙어 있습니다. 모든 상점은 길이가 $E$($1 \le E \le 500$) 마일인 X축 구간 위에 있습니다. 상점 $i$는 위치 $X_i$($0 < X_i < E$)에 있고, 사료를 파운드당 $C_i$($1 \le C_i \le 10,000,000$) 센트에 최대 $F_i$($1 \le F_i \le 10,000$) 파운드까지 팝니다. 같은 위치에 상점이 둘 이상 있을 수도 있습니다.

FJ는 위치 $0$에서 출발해 양의 방향으로만 이동할 수 있으며, 위치 $E$에 도착할 때 사료를 최소 $K$ 파운드 실은 상태여야 합니다. 가는 길에 어떤 상점에든 들러 그 상점의 한도까지 원하는 만큼 살 수 있습니다.

FJ가 사료 $K$ 파운드를 사서 운반하는 데 드는 최소 총비용은 얼마일까요? 상점 전체의 재고로 필요한 양을 반드시 채울 수 있음이 보장됩니다.

예를 들어 FJ가 $2$ 파운드가 필요하고, $0 \ldots 5$ 범위의 수직선 위 위치 $1$, $3$, $4$에 상점이 하나씩 있다고 합시다.

      0   1   2   3   4   5   X
      +---|---+---|---|---+
          1       1   1
          1       2   2

각 상점 아래 첫 번째 숫자 줄은 팔 수 있는 파운드 수이고, 두 번째 줄은 파운드당 가격(센트)입니다. 즉 위치 $1$의 상점은 $1$ 파운드를 $1$ 센트에, 위치 $3$과 $4$의 상점은 각각 $1$ 파운드를 $2$ 센트에 팝니다.

가장 저렴한 방법은 위치 $3$과 $4$의 상점에서 각각 $1$ 파운드씩 사는 것입니다. 사료값은 $2 + 2 = 4$ 센트입니다. 위치 $0$에서 $3$까지는 사료를 싣지 않아 운반비가 $0$입니다. $3$에서 $4$로 갈 때는 $1$ 파운드를 싣고 $1$ 마일을 움직이므로 $1 \times 1 \times 1 = 1$ 센트, $4$에서 $5$로 갈 때는 $2$ 파운드를 싣고 $1$ 마일을 움직이므로 $1 \times 2 \times 2 = 4$ 센트가 듭니다. 총비용은 $4 + 1 + 4 = 9$ 센트입니다.

• 첫째 줄: 공백으로 구분된 세 정수 $K$, $E$, $N$.
• 둘째 줄부터 $N+1$째 줄까지: $i+1$째 줄에는 공백으로 구분된 세 정수 $X_i$, $F_i$, $C_i$가 주어집니다.

• 한 줄에 정수 하나: FJ가 사료를 사서 운반하는 최소 총비용.