Cabbage

The <> Children of the Volga Plain are known to be very fond of pickled cabbage. However, each of them has a favorite cabbage variety and will not eat any other kind. The preferences seem to be random. Different Children can like either different or the same varieties of cabbage. To make everyone happy, the portions must be the same. Alchen, the chief, wants to make the portions as big as possible.

Initially, Alchen has a certain stock of each cabbage variety and a certain sum of money. He can buy extra cabbage with this money, a different amount of each variety. The prices are known. However, he cannot sell the cabbage he already has.

Help Alchen figure out the best portion sizes for his proteges.

The first line of the input file contains a single integer $T$, the number of test cases ($1 \le T \le 100$). It is followed by $T$ blocks.

The first line of a block contains three integers: $N$, the number of pickled cabbage varieties ($1 \le N \le 10^5$), $M$, the number of hungry Children ($1 \le M \le 10^5$), and $S$, the sum of money allocated for buying extra pickled cabbage ($1 \le S \le 10^9$).

The second line of a block contains $M$ integers $T\_i$, where $T\_i$ is the number of the pickled cabbage variety preferred by the $i$-th Child of the Volga Plain ($1 \le T\_i \le N$).

Each of the following $N$ lines contains two integers: $A\_i$, the initially available amount of cabbage of the $i$-th variety, in kilograms ($0 \le A\_i \le 10^4$), and $C\_i$, the price of a kilogram of cabbage of this variety ($1 \le C\_i \le 10^4$).

The sum of $M$ over all test cases is at most $10^5$, and the sum of $N$ over all test cases is at most $10^5$.

The output file must contain $T$ lines, and the $i$-th line must contain the answer to the $i$-th test case. The answer to a test is the maximum possible portion size, in kilograms.

The absolute or relative error of each answer must be at most $10^{-9}$.