Problem Description

Xiao Lan likes eating chocolate very much, and he eats one bar of chocolate every day.

One day, Xiao Lan goes to the supermarket to buy some chocolate. There are many kinds of chocolate on the shelves. Each kind has its own price, quantity, and remaining shelf life in days. Xiao Lan only eats chocolate that has not expired. Please find the minimum cost for Xiao Lan to buy enough chocolate to last for $x$ days.

Input Format

The first line contains two integers $x$ and $n$, which represent the number of days Xiao Lan needs to eat chocolate and the number of chocolate types.

The next $n$ lines describe the chocolates on the shelf. The $i$-th line contains three integers $a_i$, $b_i$, and $c_i$, meaning that the unit price of the $i$-th type is $a_i$, the shelf life has $b_i$ days remaining (it can be eaten within the next $b_i$ days from now), and the quantity is $c_i$.

Output Format

Output one integer representing Xiao Lan's minimum cost. If there is no purchase plan that allows Xiao Lan to eat chocolate for $x$ days, output $-1$.

10 3
1 6 5
2 7 3
3 10 10

18

Hint

Sample Explanation

One optimal plan is to buy $5$ bars of type $1$, $2$ bars of type $2$, and $3$ bars of type $3$. Eat type $1$ for the first $5$ days, type $2$ on days $6$ and $7$, and type $3$ from day $8$ to day $10$.

Constraints and Notes

For $30\%$ of the testdata, $n, x \le 1000$.

For all testdata, $1 \le n, x \le 10^5$, $1 \le a_i, b_i, c_i \le 10^9$.

Lanqiao Cup 2021 National Contest, Group C, Problem I.

Translated by ChatGPT 5