Trong một hệ thống blockchain, thợ đào chọn các giao dịch đang chờ (giả sử có N giao dịch) để đưa vào một khối mới. Mỗi giao dịch thứ i có phí Fi và kích thước Si (với 1=1,2,...,N) và Fi, Si là các số nguyên dương. Khối có kích thước tối đa Smax (Smax là số nguyên dương). Thợ đào muốn tối đa tổng phí Fi sao cho tổng kích thước Si không vượt Smax.

Giả sử rằng có D ràng buộc phụ thuộc: nếu giao dịch A được chọn thì giao dịch B cũng phải được chọn. Các phụ thuộc này không tạo thành chu trình.

Yêu cầu: Tìm tổng phí giao dịch lớn nhất.

Dữ liệu: Vào từ file văn bản BLOCKOPT.INP:

• Dòng 1: N, Smax (1≤ N ≤ 50, 1≤ Smax ≤1000).

• N dòng tiếp: Fi, Si (1< Fi, Si ≤1000) cho giao dịch i.

• Dòng tiếp: D (0 ≤ D ≤ N(N-1)/2)

• D dòng tiếp (nếu D>0): A, B (thể hiển cho ràng buộc nếu chọn A phải chọn B, trong đó A,B là chỉ số các giao dịch đang chờ A,B € {1,2,.,N}). Kết quả: Ghi ra file văn bản BLOCKOPT.OUT tổng phí lớn nhất.

Input 01:

3 10
10 5
7 4
3 3
1
1 2

Output 01:

17

Input 02:

3 10
10 5
10 5
5 3
0

Output 02:

20

Input 03:

2 10
100 11
200 12
0

Output 03:

0