Nguồn: https://www.codechef.com
Quản lý dự án và tư vấn dịch
vụ ở trường đại học BerLand luôn luôn thu hút được rất nhiều thí sinh ở Berland
đăng ký dự thi. Năm nay, N học sinh
tham gia dự thi, nhưng không có quá K em sẽ được vào trường. Để quyết định xem
ai sẽ được chọn, có một loạt bài thi đầu vào. Tất cả học sinh có tổng số điểm
lớn hơn ít nhất (N-K) bạn khác sẽ
được chọn.
Có tất cả E bài thi đầu vào, điểm số của mỗi bài
thi nằm trong khoảng từ 0 đến M. E-1
bài đã được trải qua, và giờ là lúc diễn ra bài cuối cùng.
Sergey là một học sinh rất
muốn được vào đại học, do đó anh ta đã thu thập thông tin về E-1 bài thi trước đó của tất cả N-1 thí sinh khác ( tất cả trừ anh ta
). Đương nhiên, anh ta cũng biết điểm số của chính mình.
Để ước tính cơ hội vào đại
học sau bài thi cuối, Sergey đến gặp một tiên tri. Saau chuyến đi, anh ta biết
được điểm số của tất cả cáác thí sinh khác trừ mình trong bài thi cuối. Giờ anh
ta muốn tính toán số điểm ít nhất cần đạt được để có thể vào trường đại học.
Nhưng lúc này anh ta vẫn đang bận rộn với việc ít lợi nhuận kiế m được từ cửa
hàng, nên muốn nhờ bạn giúp.
Dữ liệu
vào:
·
Dòng đầu
tiên của input chứa một số tự nhiên T
– số lượng test.
·
Dòng đầu
tiên của mỗi test chứa 4 số nguyên N, K,
E, M lần lượt là số học sinh, số học sinh lớn nhất được chọn, tổng số bài
thi và điểm lớn nhất của một bài thi.
·
N-1 dòng tiếp theo, mỗi dòng chứa
E số nguyên, trong đó E-1 số đầu
tươơng ứng với điểm số của những bài
thi đã trải qua. Số nguyên cuối cùng là điểm số của bài thi cuối cùng mà tiên
tri dự đoán.
·
Dòng
cuối cùng chứa E-1 số nguyên là điểm
số của Sergey trong E-1 bài thi đầu.
Dữ liệu
ra:
·
Với mỗi
test, in ra một dòng duy nhất chứa điểm số tối thiểu mà Serggey cần đạt được
trong bài thi cuối để có thể được chọn. Nếu Sergey không có cơ hội nào, in ra
“impossible” ( không có ngoặc kép ).
Ràng
buộc:
·
1 ≤ T ≤ 5
·
1 ≤ K < N ≤ 104
·
1 ≤ M ≤ 109
·
1 ≤ E ≤ 4
Input
1
4 2 3 10
7 7 7
4 6 10
7 10 9
9 9
Output:
4
Giải
thích:
Ví dụ 1.
Nếu Sergey đạt 4 điểm trong
bài thi cuối, điểm số của anh ta là 9+9+4=22. Sẽ đạt vị trí thứ hai trong toàn bộ thí sinh – người đầu đạt 21, người thứ hai
đạt 20 và người thứ ba đạt 26. Do vậy, Sergey sẽ được vào trường đại học.
