버스 무선 네트워크 대역폭

버스와 기차에 승객을 끌어들이거나 붙잡아 두기 위해 추가되는 편의 시설 중 하나가 무선 네트워크입니다. 덕분에 통근하는 사람은 이동 중에도 일을 처리하거나, 집에서처럼 인터넷을 즐길 수 있습니다. 물론 이용자가 많아질수록 한 사람에게 돌아가는 대역폭은 줄어들어 서비스의 매력이 다소 떨어집니다. 큰 파일을 내려받기 전에 누가 언제 버스에 타고 내리는지 미리 안다면, 이번 탑승 동안 내가 받을 대역폭을 정확히 계산할 수 있어 좋지 않을까요?

이를 계산하는 프로그램을 작성하세요. 다음 정보가 주어집니다.

1. 버스 노선: 정류장의 수와, 인접한 두 정류장 사이의 이동 시간(초).
2. 무선 네트워크: 전체 대역폭은 초당 1메가바이트입니다. 각 좌석 $i$에는 그 좌석이 차지하는 대역폭 비율 $a_i$가 주어집니다. 사람이 앉아 있는 좌석들의 집합을 $S$라 하면, 좌석 $i \in S$는 $\dfrac{a_i}{\sum_{j \in S} a_j}$ 만큼의 대역폭을 받습니다. 서로 다른 좌석의 비율 $a_i$는 모두 다릅니다. 예를 들어 비율이 각각 3, 2, 1인 세 좌석이 있다고 합시다. 앞의 두 좌석에만 사람이 있으면 첫 번째 좌석의 사람은 전체 대역폭의 $3/5 = 60\%$를, 다른 사람은 $2/5 = 40\%$를 받습니다. 세 좌석 모두 차 있으면 첫 번째 사람은 $3/6 = 50\%$, 두 번째 사람은 $2/6 \approx 33.333\%$, 세 번째 사람은 $1/6 \approx 16.667\%$를 받습니다.
3. 승객: 각 승객(나 자신 포함)이 어느 정류장에서 타고 내리는지. 같은 정류장에서는 내리는 승객이 모두 내린 뒤에 타는 승객이 탑니다. 승객은 탑승할 때 항상 (비율 기준으로) 가장 좋은 빈 좌석을 고르며, 이후 더 좋은 좌석이 비더라도 자리를 옮기지 않습니다. 버스에 빈자리가 없으면 그 승객은 타지 못합니다(나 자신도 예외가 아닙니다). 같은 정류장에서 여러 승객이 타려 하면 입력에 나열된 순서대로 시도합니다.

첫 줄에 데이터 집합의 개수 $K$가 주어집니다. 이어서 $K$개의 데이터 집합이 각각 다음 형식으로 주어집니다.

첫 줄에 네 정수 $n, m, p, y$가 주어집니다. $n$은 정류장의 수($2 \le n \le 100$), $m$은 버스 좌석의 수($1 \le m \le 100$), $p$는 승객의 수이며, $y$($1 \le y \le p$)는 승객 중 나의 번호입니다.

다음 줄에는 $n-1$개의 정수가 주어지며, 정류장 $i$에서 정류장 $i+1$까지의 이동 시간(초)을 나타냅니다. 그다음 줄에는 $m$개의 음이 아닌 정수가 주어지며, 좌석 $i$가 차지하는 비율 $a_i$를 나타냅니다.

이어서 $p$개의 줄에 각 승객 $j$의 정보가 주어집니다. 각 줄에는 두 정수, 승객이 타는 정류장 $s_j$와 내리는 정류장 $t_j$($t_j > s_j$)가 있습니다. 승객들은 타는 정류장 $s_j$가 감소하지 않는 순서로 정렬되어 있습니다.

각 데이터 집합마다 먼저 한 줄에 Data Set x:를 출력합니다($x$는 데이터 집합의 번호). 그다음 줄에 내가 얻은 전체 대역폭(메가바이트)을 소수 둘째 자리까지 반올림하여 출력합니다. 연속한 두 데이터 집합 사이에는 빈 줄을 하나 넣습니다.