题目描述

商店有 $N$ 件不同的商品，每件至多购买一次。预算为 $M$。在剩余预算买得起的商品中，每次先选优先级数值最小的，数值相同时选价格最低的，仍相同时选名字典序最小的。扣除价格后继续购买，直到没有能买的商品。

输入格式

首行给出 $M,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 M,P_i\le10^5$，$1\le N\le10^3$，$1\le V_i\le10$。商品名互不相同，只含小写字母，长度为 1 至 10。

来源

洛谷 B4452 · CCF GESP C++ 四级。