Một cửa hàng có ~N~ món hàng, món hàng thứ ~i~ có giá là ~c_i~ và có giá trị là ~v_i~. Bạn có tổng cộng ~M~ xu để chi tiêu. Bạn phải mua một số lượng món quà sao cho tổng giá trị của các món quà đó là tối đa. Tuy nhiên, có ~K~ combo dạng ~(a_i, b_i)~: nếu bạn mua món ~a_i~ thì bạn bắt buộc phải mua món ~b_i~.

Yêu cầu: Xác định tổng giá trị lớn nhất của các món hàng mà bạn có thể mua.

Input

• Dòng đầu tiên ghi 3 số nguyên dương ~N, M, K~.
• Mỗi dòng thứ ~i~ trong ~N~ dòng tiếp theo ghi 2 số nguyên dương ~c_i, v_i~ lần lượt là giá và giá trị của vật thứ ~i~.
• Mỗi dòng thứ ~j~ trong ~K~ dòng tiếp theo ghi 2 số nguyên dương ~a_j, b_j~ thể hiện rằng khi bạn mua món hàng ~a_j~ thì phải mua món hàng ~b_j~.

Output

• In ra một dòng duy nhất chứa một số nguyên dương là tổng giá trị cao nhất của các món hàng mà bạn có thể mua.

Sample Input 1

5 10 3
3 4
4 5
2 3
5 10
1 2
1 3
4 5
3 4

Sample Output 1

17