Entrance Exam

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
The faculty of application management and consulting services (FAMCS) of the Berland State University (BSU) has always been popular among Berland's enrollees. This year, N students attended the entrance exams, but no more than K will enter the university. In order to decide who are these students, there are series of entrance exams. All the students with score strictly greater than at least (NK) students' total score gets enrolled.
In total there are E entrance exams, in each of them one can score between 0 and M points, inclusively. The first E1 exams had already been conducted, and now it's time for the last tribulation.
Sergey is the student who wants very hard to enter the university, so he had collected the information about the first E1 from all N1 enrollees (i.e., everyone except him). Of course, he knows his own scores as well.
In order to estimate his chances to enter the University after the last exam, Sergey went to a fortune teller. From the visit, he learnt about scores that everyone except him will get at the last exam. Now he wants to calculate the minimum score he needs to score in order to enter to the university. But now he's still very busy with minimizing the amount of change he gets in the shops, so he asks you to help him.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains four space separated integers N, K, E, M denoting the number of students, the maximal number of students who'll get enrolled, the total number of entrance exams and maximal number of points for a single exam, respectively.
The following N1 lines will contain E integers each, where the first E1 integers correspond to the scores of the exams conducted. The last integer corresponds to the score at the last exam, that was predicted by the fortuneteller.
The last line contains E1 integers denoting Sergey's score for the first E1 exams.
Output
For each test case, output a single line containing the minimum score Sergey should get in the last exam in order to be enrolled. If Sergey doesn't have a chance to be enrolled, output "Impossible" (without quotes).
Constraints
 1 ≤ T ≤ 5
 1 ≤ K < N ≤ 10^{4}
 1 ≤ M ≤ 10^{9}
 1 ≤ E ≤ 4
Example
Input: 1 4 2 3 10 7 7 7 4 6 10 7 10 9 9 9 Output: 4
Explanation
Example case 1. If Sergey gets 4 points at the last exam, his score will be equal to 9+9+4=22. This will be the second score among all the enrollees  the first one will get 21, the second one will get 20 and the third will have the total of 26. Thus, Sergey will enter the university.
Author:  xcwgf666 
Tester:  
Editorial  http://discuss.codechef.com/problems/ENTEXAM 
Tags  loop, simple, snckpb16, xcwgf666 
Date Added:  13052015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 