Input

4 2 2
1 2 3 4
1 4
3 4

Output

13

Input

4 2 5
1 2 0 0
1 4
3 4

Output

0

Nguồn: Thanh Hoàng