Farmer John jedzie po $K$ ($1 \le K \le 10,000$) funtów paszy. Mila z $K$ kosztuje $K*K$ centów, $D$ mil $D*K*K$.

$N$ ($1 \le N \le 500$) sklepów $1..N$ na osi $X$, odcinek długości $E$ ($1 \le E \le 500$) mil. Sklep $i$ w $X_{i}$ ($0 < X_{i} < E$), do $F_{i}$ ($1 \le F_{i} \le 10,000$) funtów po $C_{i}$ ($1 \le C_{i} \le 10,000,000$) centów za funt. Kilka sklepów może być w jednym punkcie.

Od 0 tylko dodatnio, przyjazd $E$ z co najmniej $K$. Dowolne postoje i zakup ilości do limitu sklepu.

Znajdź minimum zakupu i przewozu $K$. Wiadomo, że wystarczy paszy.

Dwa funty, sklepy 1,3,4 na $0..5$:

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

Najlepiej po funcie w drugim i trzecim, po 2 centy, zakup 4. 0–3 bez ładunku gratis; 3–4 mila z funtem kosztuje $1*1*1 = 1$ cent.

4–5 mila z dwoma kosztuje $1*2*2 = 4$ centy.

Zakup $2+2$, przewóz $1+4$, razem $2 + 2 + 1 + 4 = 9$ centów.

Wejście

• Wiersz 1: całkowite $K$, $E$, $N$ ze spacjami.
• Wiersze $2..N+1$: wiersz $i+1$, całkowite $X_{i}$, $F_{i}$, $C_{i}$ ze spacjami.

Wyjście

• Wiersz 1: całkowite, minimum zakupu i przewozu.

Przykład

Wejście 1

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

Wyjście 1

9

Autor zadania: Tom Conerly, 2009