25048번 - 랜선 연결

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

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

현재 연구실에는 $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을 출력합니다.