内存限制:128 MB
时间限制:1 S
标准输入输出
题目类型:传统
评测方式:文本比较
上传者:
提交:3
通过:1
小蓝很喜欢吃巧克力,他每天都要吃一块巧克力。
一天小蓝到超市想买一些巧克力。超市的货架上有很多种巧克力,每种巧克力有自己的价格、数量和剩余的保质期天数,小蓝只吃没过保质期的巧克力,请问小蓝最少花多少钱能买到让自己吃 $x$ 天的巧克力。
https://www.luogu.com.cn/problem/P8769
输入的第一行包含两个整数 $x$,$n$,分别表示需要吃巧克力的天数和巧克力的种类数。
接下来 $n$ 行描述货架上的巧克力,其中第 $i$ 行包含三个整数 $a_i$,$b_i$,$c_i$,表示第 $i$ 种巧克力的单价为 $a_i$,保质期还剩 $b_i$ 天(从现在开始的 $b_i$ 天可以吃),数量为 $c_i$。
输出一个整数表示小蓝的最小花费。如果不存在让小蓝吃 $x$ 天的购买方案,输出 $−1$。
**【样例说明】**
一种最佳的方案是第 $1$ 种买 $5$ 块,第 $2$ 种买 $2$ 块,第 $3$ 种买 $3$ 块。前 $5$ 天吃第 $1$ 种,第 $6$、$7$ 天吃第 $2$ 种,第 $8$ 至 $10$ 天吃第 $3$ 种。
**【评测用例规模与约定】**
对于 $30\%$ 的评测用例,$n,x \le 1000$。
对于所有评测用例,$1\le n,x\le 10^5$,$1 ≤ a_i,b_i ,c_i\le10^9$。