题目描述

旅游协调员泽贝尔（Zebel）为他的客户预订了有限数量的酒店房间。不同房间的容量不同，价格自然也不同。泽贝尔决定以最低的成本为旅行参与者分配可用的房间。他的策略是合理安排人员入住，以最小化总体房间成本，但他面临一些限制条件：不同性别的未婚人士不得同住一个房间，并且如果一个房间分配给已婚夫妇，则不得再入住其他任何人。请注意，已婚夫妇不一定要住在同一个房间，而且房间也不必住满。

你需要编写一个程序，帮助泽贝尔找到将旅行参与者分配到预订酒店房间的最低成本方案。

输入

第一行只有一个数字$t$，表示接下来的测试用例数量。每个测试用例的第一行包含四个整数：$0 \leq m \leq 500$（男性旅行参与者的数量）、$0 \leq f \leq 500$（女性旅行参与者的数量）、$0 \leq r \leq 500$（泽贝尔预订的房间数量）和$c \geq 0$（旅行参与者之间的婚姻关系数量）。请注意，旅行中不允许一夫多妻制；即每个参与者要么单身，要么有唯一的配偶。

接下来的$r$行描述预订的房间。每行用两个整数$1 \leq b_i \leq 5$和$1 \leq p_i \leq 1000$描述一个房间，分别表示该房间的容量和价格。

输出

对于输入中的每个测试用例，输出将房间分配给旅行参与者的最低成本。如果无法分配，输出"Impossible"。

输入样例 1

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

输出样例 1

9
Impossible

来源

Tehran 2005