题目背景

2025 年 12 月 GESP C++ 四级编程第 2 题

题目描述

小 A 有 $M$ 元预算。商店有 $N$ 个商品，每个商品有商品名 $S$、价格 $P$ 和优先级 $V$ 三种属性，其中 $V$ 为正整数，且 $V$ 越小代表商品优先级越高。

小 A 的购物策略为：

• 总是优先买优先级最高的东西；
• 如果有多个最高优先级商品，购买价格最低的；
• 如果有多个优先级最高且价格最低的商品，购买商品名字典序最小的。

每次买入一个商品后预算减少对应价格；若当前按策略选出的商品价格超过剩余预算，则停止购买。请输出最终购买的所有商品名。

输入格式

第一行输入两个正整数 $M,N$，表示预算和商品数。

接下来 $N$ 行，每行输入一个商品的信息 $S_i P_i V_i$。

数据保证不存在两个名字相同的商品。

输出格式

按照字典序从小到大的顺序，输出所有购买商品的商品名，每行一个。

20 4
apple 6 8
bus 15 1
cab 1 10
water 4 8

bus
cab
water

数据范围与提示

• $1 \le |S_i| \le 10$
• $1 \le M,P_i \le 10^5$
• $1 \le N \le 10^3$
• $1 \le V_i \le 10$
• 商品名仅由小写字母组成且互不相同

样例中先买优先级最高的 bus，再在优先级为 $8$ 的商品中按价格买 water，最后还能买 cab，输出时按字典序排列。