호텔 예약

홍준이는 여행사에서 일한다. 여행사는 남자 m명과 여자 f명을 주어진 호텔 방들에 배정하려고 한다. 이들 중 c쌍은 서로 결혼한 부부이다. 각 방에는 최대 인원과 대여 비용이 정해져 있다.

사람들을 방에 배정할 때는 다음 조건을 모두 만족해야 한다.

1. 서로 결혼하지 않은 남자와 여자는 같은 방을 사용할 수 없다.
2. 결혼한 남자와 여자가 같은 방을 사용한다면, 그 방에는 두 사람만 들어갈 수 있다.
3. 결혼한 부부가 반드시 같은 방을 사용해야 하는 것은 아니다.

모든 사람에게 방을 배정하는 데 필요한 최소 비용을 구하시오.

첫째 줄에 남자의 수 m (1 ≤ m ≤ 100), 여자의 수 f (1 ≤ f ≤ 100), 방의 수 r (1 ≤ r ≤ 100), 결혼한 부부의 수 c (0 ≤ c ≤ min(m, f))가 공백으로 구분되어 주어진다.

다음 r개 줄에는 각 방의 정보가 주어진다. 각 줄에는 두 정수 a와 b가 공백으로 구분되어 주어지며, 1 ≤ a ≤ 5, 1 ≤ b ≤ 1000이다. a는 그 방에 들어갈 수 있는 최대 인원이고, b는 그 방을 빌리는 비용이다.

모든 사람에게 방을 배정할 수 있다면 방을 빌리는 데 필요한 최소 비용을 출력한다. 불가능하다면 Impossible을 출력한다.