Farmer John jedzie do miasta po $K$ funtów paszy ($1 \le K \le 100$). Przejazd $D$ mil z $K$ funtami na ciężarówce kosztuje $D*K$ centów.

Targ hrabstwa ma $N$ sklepów ($1 \le N \le 100$), numerowanych $1..N$, na odcinku osi $X$ długości $E$ ($1 \le E \le 350$). Sklep $i$ leży w $X_{i}$ ($0 < X_{i} < E$), sprzedaje do $F_{i}$ funtów ($1 \le F_{i} \le 100$) po $C_{i}$ centów za funt ($1 \le C_{i} \le 1,000,000$). W jednym punkcie osi $X$ może być kilka sklepów.

FJ zaczyna w 0 i jedzie tylko w dodatnim kierunku, docierając do $E$ z co najmniej $K$ funtami. Może zatrzymać się w dowolnym sklepie po drodze i kupić dowolną ilość do jego limitu.

Jaki jest minimalny koszt zakupu i transportu $K$ funtów? FJ wie, że istnieje rozwiązanie.

Na przykład potrzebuje dwóch funtów z trzech sklepów w 1, 3, 4 na prostej $0..5$:

      0   1   2   3   4   5
      +---|---+---|---|---+
          1       1   1      Dostępne funty paszy
          1       2   2      Centy za funt

Najlepiej kupić po funcie w drugim i trzecim sklepie, każdy za dwa centy, razem 4. Od 3 do 4 jedzie 1 jednostkę z 1 funtem, płacąc $1*1 = 1$ cent.

Od 4 do 5 jedzie 1 jednostkę z 2 funtami, płacąc $1*2 = 2$ centy.

Razem $4+1+2 = 7$ centów.

Wejście

• Wiersz 1: trzy całkowite $K$, $E$, $N$ oddzielone spacjami.

• Wiersze $2..N+1$: wiersz $i+1$ zawiera trzy całkowite $X_{i}$, $F_{i}$, $C_{i}$ oddzielone spacjami.

Wyjście

• Wiersz 1: jedna całkowita, minimalny koszt zakupu i transportu paszy.

Przykład

Wejście 1

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

Wyjście 1

7

Autor zadania: Tom Conerly, 2009