Farmer John은 마을에 가서 사료 $K$파운드 ($1 \le K \le 100$)를 사야 한다. 트럭에 $K$파운드를 싣고 $D$마일 이동하면 $D*K$센트가 든다.

군의 사료 시장에는 $1..N$으로 번호 매긴 상점 $N$개 ($1 \le N \le 100$)가 있으며, 길이 $E$ ($1 \le E \le 350$)인 $X$축 선분에 있다. 상점 $i$의 위치는 $X_{i}$ ($0 < X_{i} < E$), 판매 한도는 $F_{i}$파운드 ($1 \le F_{i} \le 100$), 파운드당 가격은 $C_{i}$센트 ($1 \le C_{i} \le 1,000,000$)이다. $X$축의 한 위치에 여러 상점이 있을 수 있다.

FJ는 0에서 출발해 양의 방향으로만 이동하며, 마지막에 적어도 $K$파운드를 가진 채 $E$에 도착한다. 도중 어느 상점에서든 멈춰 상점의 한도까지 임의의 양을 살 수 있다.

$K$파운드를 구매하고 운반하는 최소 비용은 얼마인가? FJ는 해가 있음을 안다.

예를 들어 $0..5$의 수직선 위 1, 3, 4에 있는 세 상점에서 2파운드를 사야 한다면:

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

두 번째와 세 번째 상점에서 1파운드씩 사는 것이 최선이다. 각각 2센트로 구매 비용은 총 4이다. 3에서 4로 길이 1을 1파운드를 싣고 이동하면 $1*1 = 1$센트가 든다.

4에서 5로 길이 1을 2파운드를 싣고 이동하면 $1*2 = 2$센트가 든다.

총 비용은 $4+1+2 = 7$센트이다.

입력

• 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

7

문제 출제자: Tom Conerly, 2009