LAN Cable Connection

Interview

Time limit1.5sMemory limit1024 MB

Summary

Choose a nonempty set of switches with minimum total cost so their ports exactly fit M computers plus one uplink cable, or report -1 if impossible.

Level: Medium5 of 10
Topics: Dynamic programming, Math
Solved: No attempts yet

Problem

Eunkyu and the lab members recently moved to a new lab, and they hit a big snag: the new lab has no internet connection.

Luckily, they got one LAN cable with internet access from the neighboring lab. They can connect this cable to a switch in the lab to bring the internet in.

The lab has $N$ switches (network switches) and $M$ computers. Each switch has $a_i$ ports and costs $b_i$ to install. To supply internet from a switch, one cable carrying internet must be connected, and it can supply internet to $a_i - 1$ other devices (switches or computers). Switches cannot form a cycle, because that creates a fire hazard.

Eunkyu likes neat wiring, so he wants no unused ports on the switches. He also cares about efficiency, so if several wiring plans are possible, he picks the one with the lowest cost that still supplies every computer. If such a wiring is possible, print the minimum cost of it. If not, print -1.

Input

The first line contains the number of switches $N$ ( $1 \le N \le 300$ ).

Each of the next $N$ lines contains two integers $a_i$ ( $2 \le a_i \le 10^5$ ) and $b_i$ ( $0 \le b_i \le 10^9$ ), separated by a space. They are the number of ports and the installation cost of the $i$ -th switch.

The line after those $N$ lines contains the number of computers $M$ ( $1 \le M \le 10^5$ ).

Output

On the first line, print the minimum cost among the wiring plans that satisfy the conditions. If no such plan exists, print -1.

Examples2

Example 1
Input
```
1
5 10
4
```
Expected output
```
10
```
Example 2
Input
```
1
5 10
5
```
Expected output
```
-1
```