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í ~F_i~ và kích thước ~S_i~ (với ~i=1, 2, \dots, N~) và ~F_i, S_i~ là các số nguyên dương. Khối có kích thước tối đa là ~S_{max}~ (~S_{max}~ là số nguyên dương). Thợ đào muốn tối đa tổng phí ~F_i~ sao cho tổng kích thước ~S_i~ không vượt ~S_{max}~.

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.

Input

• Dòng 1: ~N, S_{max}~ (~1 \le N \le 50, 1 \le S_{max} \le 1000~).
• ~N~ dòng tiếp theo: ~F_i, S_i~ (~1 \le F_i, S_i \le 1000~) cho giao dịch ~i~.
• Dòng tiếp: ~D~ (~0 \le D \le \frac{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 \in \{1, 2, \dots, N\}~).

Output

• Tổng phí lớn nhất.

Sample Input 1

3 10
10 5
7 4
3 3
1
1 2

Sample Output 1

17