Farmer John едет в город за $K$ фунтами корма ($1 \le K \le 100$). Проезд $D$ миль с $K$ фунтами в грузовике стоит $D*K$ центов.

На рынке округа $N$ магазинов ($1 \le N \le 100$), пронумерованных $1..N$. Они находятся на отрезке оси $X$ длины $E$ ($1 \le E \le 350$). Магазин $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 и едет только в положительном направлении, прибывая в $E$ хотя бы с $K$ фунтами. Он может остановиться в любом магазине по пути и купить любое количество в пределах его запаса.

Какова минимальная стоимость покупки и перевозки $K$ фунтов? FJ знает, что решение существует.

Например, нужны два фунта из трёх магазинов в точках 1, 3, 4 на прямой $0..5$:

      0   1   2   3   4   5
      +---|---+---|---|---+
          1       1   1      Доступные фунты корма
          1       2   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