优先购买

题目描述

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

小 A 的购物策略为：

1. 总是优先买优先级最高的东西（priority 最小）；
2. 如果有多个最高优先级商品，购买价格最低的；
3. 如果有多个优先级最高且价格最低的商品，购买商品名字典序最小的。

小 A 想知道能购买哪些商品。

输入格式

第一行两个正整数 M、N，代表预算和商品数。 之后 N 行，每行一个商品，依次为 name、price、priority，代表第 i 个商品的商品名、价格、优先级。 数据保证不存在两个名字相同的商品。

输出格式

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

样例

输入样例

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

输出样例

bus cab water

样例解释

按“优先级最小、价格最小、字典序最小”的顺序，商品排序为 bus(15,1)、water(4,8)、apple(6,8)、cab(1,10)。预算 20：先买 bus(花费 15，剩 5)，再买 water(花费 4，剩 1)，apple 花费 6 剩余不足，cab 花费 1（剩 0）。购得 bus、water、cab，按字典序输出为 bus、cab、water。

数据范围

对于所有测试点，保证 1 <= M <= 10^9，1 <= N <= 1000，1 <= price <= 10^9，1 <= priority <= 10^9。商品名仅由小写字母组成且不存在两个相同的商品名。