P8769 [Lanqiao Cup 2021 National C] Chocolate

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.

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 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$.

**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