J. Magic Balls
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Once a wise man said, "You need balls to do business". Now Mike has $$$n$$$ balls and he wants to do business, $$$i^{\text{th}}$$$ ball has color $$$c_i(1 \le c_i \le n)$$$. He will sell exactly $$$k$$$ of his balls. The price of a ball depends on its color. The price of a ball having color $$$i$$$ is $$$p_i$$$.

Mike knows $$$m$$$ types of magic operations. By applying the $$$i^{\text{th}}$$$ type of operation, he can change the color of a ball from $$$x_i$$$ to $$$y_i$$$. Before selling his balls Mike can apply as many operations as he wants on any number of balls.

What is the maximum amount of money Mike can make selling exactly $$$k$$$ balls?

Input

First line of the input contains a single integer $$$T(1 \le T \le 10)$$$ denoting number of test cases.

The first line of each test case contains three integers $$$n, m (1 \le n, m \le 10^5)$$$ and $$$k(0\le k \le n)$$$. Next line contains $$$n$$$ integer, $$$i^{\text{th}}$$$ of which denotes $$$c_i (1 \le c_i \le n)$$$. Next line contains $$$n$$$ integers, $$$i^{\text{th}}$$$ of them denotes $$$p_i(1\le p_i \le 10^9)$$$. $$$i^{\text{th}}$$$ of the next $$$m$$$ lines contains two integer $$$x_i, y_i ( 1 \le x_i , y_i \le n)$$$.

Output

For each test case, print a single integer denoting the maximum money Mike can make by selling exactly $$$k$$$ balls.

Example
Input
1
5 3 5
1 2 3 4 5
5 4 5 2 3
2 3
3 4
4 5
Output
21
Note

In the beginning, Mike uses the $$$1^{\text{st}}$$$ magic operation and changes the color of $$$2^{\text{nd}}$$$ ball from color $$$2$$$ to $$$3$$$. Then he uses the $$$3^{\text{rd}}$$$ magic to change the color of $$$4^{\text{th}}$$$ ball from color $$$4$$$ to color $$$5$$$. Thus the colors of the balls are now $$$1, 3, 3, 5, 5$$$. As the price of a ball with color $$$1$$$ and color $$$3$$$ is $$$5$$$ and a ball with color $$$5$$$ is $$$3$$$, he will get $$$5+5+5+3+3=21$$$ amount of money by selling all the balls.