324. Problem Set

Problem Statement:
It's the last training contest at Coach Abd El-Wahab's training before the ACPC. The coach has a big pool of problems from which he will choose a number of problems for the contest. As it's the last contest, the coach wants to make it neither too hard so weaker teams won't get frustrated nor too easy so that stronger teams won't get cocky. Specifically, he wants to choose a subset of problems such that the weakest team, whose name is "CodeMorning", solves exactly x problems, and the strongest team, whose name is "CodeName", solves exactly y problems. x and y are secret integers he's giving to you in the input because you're so special to him. Each team consists of 3 members. Each member has a skill level that can be summarized as an integer. A team's power is equal to the summation of its members' skill levels. Each problem has a difficulty that can also be summarized as an integer (What a coincidence!). A team is able to solve a problem if the team's power is greater than or equal to the problem difficulty. Output the subset of problems that can achieve the coach's goal, or "No Solution." instead. If there are several subsets that achieve the coach's goal, output the most difficult subset, where difficulty of a set of problems is defined as the summation of its problems' difficulties. If there is still a tie, sort the problems in non-decreasing order by difficulty and choose the problem set which is lexicographically smallest.

Input Format:
The first line contains an integer T represents the number of test cases. Each test case starts with a line containing 4 integers N, M, x, and y representing the number of teams, the number of problems the Coach has, and the secret x and y described in the statement, respectively. Then follow N lines, each of them has 3 integers, representing the skill levels of its team members. Then follows a line that has M integers separated by space, each of them representing the difficulty of a problem which the Coach has. Where (1 ≤ N ≤ 1, 000), (1 ≤ M, x, y ≤ 10), (x ≤ y), (1 ≤  Member skill level  ≤ 100, 000), and (1 ≤  Problem difficulty  ≤ 100, 000).

Output Format:
For each test case, output a line by itself containing "Case X: " , where X is the test case number starting from 1. Then on the same line output the difficulties of problems you chose in the subset that satisfy the Coach's goal in non-decreasing order of the difficulty separated by space if such subset exists, or "No Solution." otherwise (without quotes).

Sample Input:
2 3 4 1 3 1 2 3 4 5 6 7 8 9 6 7 8 9 2 2 1 2 10 10 10 20 20 20 1 1

Sample Output:
Case 1: 6 8 9 Case 2: No Solution.

 Added by: hossamyosef Added at: 2014-11-11 15:32:53 UTC Time Limit: 2 seconds Partial score: No Source: ACM Jordanian Collegiate Programming Contest 2014