PRIZES - Precious Prizes

As the winner of the competition, you are asked to take prizes that are numbered from 1 to K. Each i-prize weighs Wi kg and is worth Hi dollar. You are carrying a bag with a capacity of N kg. The gifts must be put in this bag to be taken home. Each prize must be taken in its entirety and may not be taken in certain parts. Determine which gifts need to be brought, so that the total value of the gifts brought can be as maximum as possible. You may carry a number of gifts, so that the total weight is still <= N kg.

Input

The first line contains the testcase T (1 <= T <= 100), as many as T the next line contains two integers separated by spaces, namely N and K.

The next K line contains two Wi and Hi numbers, which represent a description of a gift.

Output

Print the serial number of the prizes so that the total value is maximum. Print these numbers in order from small to large.

If there is more than one optimal prize picking method, print out a method for picking prizes that minimizes weight.

If there is more than one method, prioritize the prizes with the smaller number.

Constraints

1 ≤ N ≤ 2,000

1 ≤ K ≤ 100

1 ≤ Wi, Hi ≤ 2,000, for 1 ≤ i ≤ K

Example

Input:
2
5 3
9 3
10 2
32 2
11 3
10 30
6 17
5 14

Output:
Case 1:
0
Case 2:
2
3

Added by:wibit
Date:2021-01-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2023-01-02 17:44:04 RR
Can't the editorial board members hide these shitty problems from classical problemset? Bad description + bad problem (just basic knapsack)

Last edit: 2023-01-02 17:44:17
2021-04-18 00:26:59 Scape
The only thing worse than the problem itself is the crappy description
2021-01-30 20:30:32 Rafail Loizou
I like how the gifts became stones so suddenly.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.