Priority Purchase

Problem Description

Little A has a budget of $M$ yuan. The shop has $N$ products, each with three attributes: name $S$, price $P$, and priority $V$, where $V$ is a positive integer and a smaller $V$ means a higher priority.

Little A's shopping strategy is:

• Always buy the highest-priority item first;
• If several items share the highest priority, buy the cheapest one;
• If several items share the highest priority and the lowest price, buy the one whose name is lexicographically smallest.

Little A wants to know which products he can buy.

Input Format

The first line contains two positive integers $M$ and $N$, the budget and the number of products. The following $N$ lines each describe one product: $S_i\ P_i\ V_i$, the name, price, and priority of the $i$-th product. It is guaranteed that no two products share the same name.

Output Format

Output the names of all purchased products in lexicographically ascending order.

Sample Input

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

Sample Output

bus
cab
water

Sample Explanation

For the sample, Little A has a budget of $20$ yuan and $4$ products. First, the highest-priority product is bus (priority $1$), priced $15$ yuan; after buying it, $5$ yuan remain. Next, among the remaining products the highest priority is $8$, shared by apple (price $6$) and water (price $4$); by the rule the cheaper one is bought first, so water is bought, costing $4$ yuan and leaving $1$ yuan. Finally, among the remaining products the highest priority is cab (priority $10$), priced $1$ yuan; after buying it $0$ yuan remain. The purchase order is bus, water, cab; sorted lexicographically ascending as required, the result is bus, cab, water.

Constraints

For all test points, $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$. Product names consist only of lowercase letters, and no two are the same.