Có ~N~ giao dịch, giao dịch thứ ~i~ có phí ~F_i~ và kích thước ~S_i~. Một khối có kích thước tối đa ~Smax~. Nếu chọn giao dịch ~A~ thì bắt buộc chọn giao dịch ~B~ đối với mỗi ràng buộc phụ thuộc đã cho. Các phụ thuộc không tạo chu trình.

Hãy tìm tổng phí lớn nhất sao cho tổng kích thước không vượt quá ~Smax~ và mọi phụ thuộc đều được thỏa mãn.

Input

Dòng đầu chứa ~N, Smax~ ~(1 \le N \le 50, 1 \le Smax \le 1000)~.

~N~ dòng tiếp theo chứa ~F_i, S_i~ ~(1 \le F_i, S_i \le 1000)~.

Dòng tiếp theo chứa ~D~. Sau đó là ~D~ dòng, mỗi dòng chứa ~A, B~ nghĩa là nếu chọn ~A~ thì phải chọn ~B~.

Output

In ra tổng phí lớn nhất.

Subtask

• 100% số điểm: không có ràng buộc bổ sung ngoài các giới hạn đã nêu ở phần Input.

Ví dụ 1

3 10
10 5
7 4
3 3
1
1 2

17

Ví dụ 2

18 424
754 692
975 888
151 446
890 859
536 255
772 614
536 776
21 851
29 706
596 943
662 719
189 880
3 579
316 547
565 669
785 979
173 210
32 716
8
4 3
7 4
9 3
12 4
12 7
14 5
15 4
18 6

536