题目描述

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

小 $A$ 的购物策略为：

• 总是优先购买优先级最高的商品（即 $V$ 值最小的商品）；
• 如果有多个最高优先级商品，购买价格 $P$ 最低的；
• 如果有多个优先级最高且价格最低的商品，购买商品名 $S$ 字典序最小的。

小 $A$ 会不断按照上述策略挑选并购买商品，直到剩余预算不足以购买任何符合条件的商品。每个商品只能购买一次。请你输出小 $A$ 购买的所有商品的商品名，并按字典序从小到大排序。

输入格式

第一行包含两个正整数 $M$ 和 $N$ —— 分别代表预算和商品总数。

接下来的 $N$ 行，每行描述一个商品，依次为字符串 $S_i$、整数 $P_i$ 和整数 $V_i$，分别代表第 $i$ 个商品的商品名、价格和优先级。

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

输出格式

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

样例输入 1

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

样例输出 1

bus
cab
water

说明

样例解释

1. 小 $A$ 初始有 $20$ 元。
2. 优先级最高的是 $bus$ ($V=1$)，价格为 $15$，购买后剩余 $20-15=5$ 元。
3. 剩余商品中，优先级最高的是 $apple$ ($V=8, P=6$) 和 $water$ ($V=8, P=4$)。两者中 $water$ 价格更低，购买后剩余 $5-4=1$ 元。
4. 剩余商品中，优先级最高的是 $apple$ ($V=8, P=6$)，但预算 $1$ 元不足以购买。
5. 下一个优先级最高的是 $cab$ ($V=10, P=1$)，价格为 $1$，刚好可以购买，购买后剩余 $1-1=0$ 元。
6. 最终购买了 $bus, water, cab$ 三件商品。按字典序排序后输出为 $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$。
• 保证商品名仅由小写字母组成，且不存在两个相同的商品名。
• 保证所有的输入数值均为整数。