Hotel Reservation

Time limit2sMemory limit128 MB

Summary
Assign men, women, and married couples to rooms with capacity/cost constraints under strict cohabitation rules, minimizing total rental cost or reporting impossibility.
Level

Hard8 of 10

Topics
Greedy, Dynamic programming, Combinatorics
Solved
No attempts yet

Problem

Hongjun works at a travel agency. The agency must assign m men and f women to the given hotel rooms. Among these people, c male-female pairs are married couples. Each room has a maximum capacity and a rental cost.

The assignment must satisfy all of the following rules.

  1. A man and a woman who are not married to each other cannot share a room.
  2. If a married man and woman share a room, only those two people may stay in that room.
  3. A married couple is not required to share a room.

Find the minimum total cost needed to assign rooms to everyone.

Input

The first line contains four integers m (1 ≤ m ≤ 100), f (1 ≤ f ≤ 100), r (1 ≤ r ≤ 100), and c (0 ≤ c ≤ min(m, f)): the number of men, the number of women, the number of rooms, and the number of married couples.

Each of the next r lines contains two integers a and b, where 1 ≤ a ≤ 5 and 1 ≤ b ≤ 1000. Here, a is the maximum number of people who can stay in that room, and b is the cost of renting it.

Output

If everyone can be assigned to rooms, print the minimum total rental cost. Otherwise, print Impossible.

Examples2

  1. Example 1

    Input
    2 1 3 1
3 5
2 10
2 4
    Expected output
    9

  2. Example 2

    Input
    1 1 1 0
1 4
    Expected output
    Impossible