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.

Dữ liệu chấm được sinh theo các nhóm subtask trong đề.

Subtask

• 100% s? ?i?m: ~1 \le N \le 50~, ~1 \le Smax \le 1000~, ~1 \le F_i,S_i \le 1000~, ~0 \le D \le N(N-1)/2~.