양배추

볼가 평원의 <<배고픈>> 아이들은 절인 양배추를 매우 좋아한다. 하지만 아이마다 좋아하는 양배추 품종이 있어서 다른 품종은 먹지 않는다. 선호도는 무작위로 정해진 듯하다. 서로 다른 아이가 같은 품종을 좋아할 수도 있고 다른 품종을 좋아할 수도 있다. 모두를 만족시키려면 각자에게 주는 양을 같게 해야 한다. 우두머리 Alchen은 그 양을 최대한 크게 하고 싶다.

Alchen은 처음에 각 양배추 품종의 재고와 일정 금액의 돈을 가지고 있다. 이 돈으로 양배추를 품종별로 원하는 만큼 더 살 수 있다. 가격은 알려져 있다. 이미 가지고 있는 양배추는 팔 수 없다.

Alchen이 부하들에게 나눠 줄 최적의 양을 구하도록 도와주자.

입력 파일의 첫 줄에는 테스트 케이스의 수 $T$가 주어진다($1 \le T \le 100$). 이어서 $T$개의 블록이 온다.

각 블록의 첫 줄에는 세 정수 $N$, $M$, $S$가 주어진다. $N$은 절인 양배추 품종의 수($1 \le N \le 10^5$), $M$은 배고픈 아이의 수($1 \le M \le 10^5$), $S$는 절인 양배추를 더 사는 데 쓸 수 있는 금액($1 \le S \le 10^9$)이다.

각 블록의 둘째 줄에는 $M$개의 정수 $T\_i$가 주어진다. $T\_i$는 $i$번째 볼가 평원 아이가 좋아하는 절인 양배추 품종의 번호이다($1 \le T\_i \le N$).

이어서 $N$개의 줄이 주어지며, 각 줄에는 두 정수 $A\_i$와 $C\_i$가 있다. $A\_i$는 $i$번째 품종의 양배추가 처음에 있는 양(킬로그램)이고($0 \le A\_i \le 10^4$), $C\_i$는 이 품종 양배추 1킬로그램의 가격이다($1 \le C\_i \le 10^4$).

모든 테스트 케이스에 대한 $M$의 합은 $10^5$ 이하이고, 모든 테스트 케이스에 대한 $N$의 합도 $10^5$ 이하이다.

출력 파일에는 $T$개의 줄이 있어야 하며, $i$번째 줄에는 $i$번째 테스트 케이스의 답을 출력한다. 답은 가능한 한 사람당 양의 최댓값(킬로그램)이다.

각 답의 절대 오차 또는 상대 오차는 $10^{-9}$ 이하여야 한다.