C Programming Language

Problem Title: All You Can Eat

SOLVE IN LESS THAN O(n^2) TIME

One day, Lili was invited to eat at all you can eat restaurant by Jojo and Bibi. This restaurant has N types of dish. Each dish has various happiness and weight. There are rules in restaurants that require every portion of food ordered must be finished by the person who ordered.

Lili who does not want to lose, wants to get a total happiness of at least M. Total hap- piness can be calculated by the sum of all happiness from the food eaten.

Lili does not want to eat too much (Due to being on diet). Because she doesnt want to be seen as glutton person, Lili will only take one portion of meal she chooses. Determine the minimum total weight of food that Lili should eats.

Format Input

Input consists of one integer T - number of test case. For each test case, there are two integers N and M. Then N lines follow, and each line contains a pair of integer H_i and W_i that describe the happiness and weight for each food.

Format Output

Output should be expressed in format Case #X: Y - X is the number of the query, and followed by one integer Y , minimum weight of food that should be consumed by Lili to reach the total happiness of M, or Impossible if there is no possible answer.

Constraints

1 T 5 1 N 18 1 M 1000000000 1 H_i , W_i 1000000000

SOLVE IN LESS THAN O(n^2) TIME

Sample Input & Output (standard input & output)

2

3 7

4 2

4 3

3 2

Case #1: 4

1 4

1 1

Case #2: Impossible

PLEASE SOLVE IN LESS THAN O(n^2) TIME