Farmer John은 마을에 $K$($1 \le K \le 10,000$)파운드 사료를 사러 갑니다. $K$를 싣고 1마일 $K*K$센트, $D$마일 $D*K*K$입니다.

$N$($1 \le N \le 500$)가게 번호 $1..N$이 길이 $E$($1 \le E \le 500$)마일 $X$축 구간에 있습니다. $i$는 $X_{i}$($0 < X_{i} < E$), 최대 $F_{i}$($1 \le F_{i} \le 10,000$)파운드를 각 $C_{i}$($1 \le C_{i} \le 10,000,000$)센트로 팝니다. 한 지점 여러 가게도 가능합니다.

0에서 양의 방향만 운전해 $E$에 최소 $K$로 도착합니다. 어떤 가게나 멈춰 제한까지 임의량을 삽니다.

$K$의 구매와 운송 최소 비용을 구하세요. 충분히 살 수 있습니다.

두 파운드, $0..5$의 1,3,4에 세 가게인 예:

      0   1   2   3   4   5  X
      +---|---+---|---|---+
          1       1   1      구매 가능 파운드
          1       2   2      파운드당 센트

둘째 셋째에서 한 파운드씩 최적, 각 2센트 총 구매 4. 0–3 무부하 무료, 3–4 1마일 1파운드는 $1*1*1 = 1$센트입니다.

4–5 1마일 2파운드는 $1*2*2 = 4$센트입니다.

구매 $2+2$, 운송 $1+4$, 총 $2 + 2 + 1 + 4 = 9$센트입니다.

입력

• 1번째 줄: 공백 구분 정수 $K$, $E$, $N$.
• $2..N+1$번째 줄: $i+1$번째 줄 공백 구분 정수 $X_{i}$, $F_{i}$, $C_{i}$.

출력

• 1번째 줄: 구매와 운송 최소 비용 정수 하나.

예제

입력 1

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

출력 1

9

문제 작성자: Tom Conerly, 2009