蓝桥杯国赛每日一题：巧克力（贪心，堆）

小蓝很喜欢吃巧克力，他每天都要吃一块巧克力。

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

输入格式

输入的第一行包含两个整数 x，n，分别表示需要吃巧克力的天数和巧克力的种类数。

接下来 n 行描述货架上的巧克力，其中第 i 行包含三个整数 ai​，bi​，ci​，表示第 i 种巧克力的单价为 ai​，保质期还剩 bi​ 天（从现在开始的 bi​ 天可以吃），数量为 ci​。

输出格式

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

输入输出样例

输入 #1复制

10 3 1 6 5 2 7 3 3 10 10

输出 #1复制

18

说明/提示

【样例说明】

一种最佳的方案是第 1 种买 5 块，第 2 种买 2 块，第 3 种买 3 块。前 5 天吃第 1 种，第 6、7 天吃第 2 种，第 8至 10 天吃第 3 种。

【评测用例规模与约定】

对于 30% 的评测用例 n,x≤1000。

对于所有评测用例，1≤n,x≤10^5，1≤ai​,bi​,ci​≤10^9。

由于有些巧克力日期过期后不能再食用，