랜선 연결

최근 연구실 위치를 옮긴 은규와 연구실 사람들은 큰 난관에 봉착했습니다. 이사한 연구실에 인터넷이 연결되지 않는다는 것입니다.

다행히 이웃 연구실에서 인터넷이 연결된 랜선 한 가닥을 얻을 수 있었고, 이 랜선을 연구실의 스위치에 연결해서 인터넷을 들여올 수 있게 되었습니다.

연구실에는 $N$개의 스위치(Network Switch)와 $M$개의 컴퓨터가 있습니다. 각 스위치는 $a_i$개의 포트가 있고, 설치하는 데 $b_i$의 비용이 듭니다. 스위치에서 컴퓨터로 인터넷을 공급하려면 인터넷이 공급된 선 1개가 연결되어 있어야 하며, 이 선으로 $a_i - 1$개의 다른 기기(스위치 혹은 컴퓨터)에 인터넷을 공급할 수 있습니다. 스위치끼리 사이클을 형성하면 화재의 위험이 있으므로 불가능합니다.

은규는 깔끔한 연결을 좋아해서 스위치에 남는 포트가 없도록 연결하려고 합니다. 또 효율도 중요하게 여겨서, 가능한 연결 방식이 여러 개라면 모든 컴퓨터에 인터넷이 공급되는 방식 중 비용이 가장 적은 방식을 택합니다. 이런 연결이 가능하면 가능한 연결의 최소 비용을 출력하고, 불가능하면 -1을 출력합니다.

첫 번째 줄에 스위치의 개수 $N$ ($1 \le N \le 300$)이 주어집니다.

두 번째 줄부터 $N+1$번째 줄까지 각 줄에 정수 $a_i$ ($2 \le a_i \le 10^5$)와 $b_i$ ($0 \le b_i \le 10^9$)가 공백으로 구분되어 주어집니다. 각각 $i$번째 스위치의 포트 개수와 설치 비용을 의미합니다.

$N+2$번째 줄에는 연결할 컴퓨터의 개수 $M$ ($1 \le M \le 10^5$)이 주어집니다.

첫 번째 줄에 조건을 만족하는 연결 방식 중 최소 비용을 출력합니다. 그러한 연결 방식이 없으면 -1을 출력합니다.