Dotcpp  >  编程题库  >  蓝桥杯2021年第十二届国赛真题-巧克力
题目 2621:

蓝桥杯2021年第十二届国赛真题-巧克力

时间限制: 1s 内存限制: 128MB 提交: 1136 解决: 169

题目描述

小蓝很喜欢吃巧克力,他每天都要吃一块巧克力。
一天小蓝到超市想买一些巧克力。超市的货架上有很多种巧克力,每种巧克力有自己的价格、数量和剩余的保质期天数,小蓝只吃没过保质期的巧克力,请问小蓝最少花多少钱能买到让自己吃 x 天的巧克力。

输入格式

输入的第一行包含两个整数 x, n,分别表示需要吃巧克力的天数和巧克力的种类数。
接下来 n 行描述货架上的巧克力,其中第 i 行包含三个整数 ai, bi, ci,表示第 i 种巧克力的单价为 ai,保质期还剩 bi 天(从现在开始的 bi 天可以吃),数量为 ci。

输出格式

输出一个整数表示小蓝的最小花费。如果不存在让小蓝吃 x 天的购买方案,输出ࠪ 1。

样例输入

10 3
1 6 5
2 7 3
3 10 10

样例输出

18

提示

【样例说明】
一种最佳的方案是第 1 种买 5 块,第 2 种买 2 块,第 3 种买 3 块。前 5 天
吃第 1 种,第 6、7 天吃第 2 种,第 8 至 10 天吃第 3 种。
【评测用例规模与约定】
对于 30% 的评测用例,n, x ≤ 1000。
对于所有评测用例,1 ≤ n, x ≤ 100000,1 ≤ ai, bi, ci ≤ 109
标签