样例下载

题目描述

有 M 个男人，F 个女人（其中有 C 对夫妇）要住房。现在有 R 个房子。每个房子有床位数 Bi 和费用 Pi 。住房有以下要求：

1.每个房子住的人数不能超过 Bi。

2.夫妇不一定住在一个房间里。但一个房间如果住了一对夫妇，则不能再住其他人。

3.不考虑夫妇情况下：一个房间住了男人后，不能再住女人。对女人也是一样。

问全部入住所需的最少费用。

输入

第一行：T 表示数据组数

对于每组数据：

-第一行：M, F, R, C

-接下来 R 行，每行两个整数 Bi, Pi

输出

T 行，每组数据的答案占一行，表示全部入住所需的最少费用。如果无法全部入住，则输出 Impossible

样例输入

2
2 1 3 1
3 5
2 10
2 4
1 1 1 0
1 4

样例输出

9
Impossible

数据规模

1 <= T <=10, 0 <= M, F, R <= 500, 0 <= C <= min(M, F), 1 <= Bi <= 5, 1 <= Pi <= 1000