Time Limit: 2 second(s) | Memory Limit: 32 MB |
After graduating in CS, Mr 'AcmHateKori' has opened a cyber café. His business was running quite well unless one day he faced a problem, and with his non-ACM mind he was unable to solve that.
In his café he maintains two papers for his customers. One paper contains the entering times of the customers in the café and the other paper contains the times they have exited. He writes the times in the same order in the papers for the money calculations. And he only writes the nearest minute of the time. He writes the times from 0 to 1000 (0 means 12:00 am, 60 means 01:00 am, 730 means 02:10 pm). This idea was given by his little son.
When a person exits the café he was to pay some money. If he stays in the café for T minutes, he has to pay (T-K)^{2} paisa but not more than G paisa (if money exceeds G). It's guaranteed that every person stays at least one minute in the café.
Now one day his little son came to the café and took the paper that contained the entering times of the customers. He took a new paper and wrote the entering times randomly and threw the old paper. When his father came, he found two papers, where the first one contained some random entering times. He was at a loss and angry. Cause how can he find the total money given by the customers since for an entering time there can be multiple exiting times.
So, finally he realized the importance of ACM in life and asked you to find the minimum and maximum money he could earn by matching all entering times and exiting times. His son can be faulty. So, you have to report that too.
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a line containing three integers n (1 ≤ n ≤ 50), K (1 ≤ K ≤ 1000), G (0 ≤ G ≤ 10000) where n denotes the number of customers. The next line contains n space separated integers denoting the entering times of the customers. The next line contains n space separated integers denoting the exiting times of the customers. All the given times will lie in the range [0, 1000].
For each case, print the case number, the minimum and maximum money he could earn or 'impossible' if his son had made some mistakes.
Sample Input |
Output for Sample Input |
2 3 7 11 8 9 10 9 11 20 2 10 10 1 11 2 9 |
Case 1: 31 33 Case 2: impossible |
Developed and Maintained by
JANE ALAM JAN |
Copyright © 2012
LightOJ, Jane Alam Jan |