Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2930
The Worst Schedule

Time Limit: 2 Seconds      Memory Limit: 65536 KB

The Worst Schedule

To make the life regular, I made a schedule to arrange the things. However, it was found that no event could happen at the arranged time. That was to say, I had to pay for the lost of delay or advance. Still I had the chance to choose to have the event advance or delay to minimize the lost. But there were some dependancies among the events. Event B has dependancy on event A means if event A is delayed, event B has to be delayed too. Because of the dependancies, I found it hard to minimize the lost. So I ask you for help.


The first line of each test case contains a positive integer N <= 200, the number of events in the schedule. The second line contains N integers, the i-th of which indicates the lost of the i-th event if the i-th event is advance. The third line also contains N integers indicating the lost of the delay of the events. Each cost does not exceed 1000000. The fourth line contains one integer M, then M lines follow to indicate the dependancies the events. The line containing A B means that event B has depandancy on event A. The events are numbered from 1 to N. Each dependancy may exist at most once.


Output two integers seperated by one space in one line for each test case. The first integer tells the minimum total cost and the second one tells the maximum number of events that can be advanced to minize th total lost.

Sample Input

10 5
3 7
1 2
10 10
10 10

Sample Output

10 0
20 2

Author: GUAN, Yao
Source: ZOJ Monthly, February 2008
Submit    Status