题目描述

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

小 A 的购物策略为：

• 总是优先买优先级最高的商品；
• 若优先级相同，购买价格最低的；
• 若优先级与价格都相同，购买字典序最小的商品。

小 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

初始预算 $M=20$。

商品按规则优先级排序与选择过程：

• 优先级 1：bus（15），购买
• 优先级 8：water（4）、apple（6），先 water 再 apple，但 apple 超预算不可继续（或无法购买时停止，取决于预算变化）
• 优先级 10：cab（1），可购买

最终购买：bus、cab、water（输出按字典序排序）

数据范围

$1 \leq |S_i| \leq 10$，$1 \leq M, P_i \leq 10^5$，$1 \leq N \leq 10^3$，$1 \leq V_i \leq 10$，商品名为小写字母且互不相同。