|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||128 MB||4||3||3||75.000%|
One amenity that is being added to buses and trains in order to attract or retain ridership is wireless networks. This way, commuters can get work done, or waste as much time browsing the Internet as they do at home. Of course, as more and more riders use the service, there is less and less bandwidth available for any one person, making the service somewhat less attractive. Wouldn’t it be nice if, before downloading a big file, you knew who would enter and leave a bus when, so you could calculate exactly how much bandwidth you will get over the course of your ride?
You should write a program to help you compute this. You will be given the following data:
The first line contains the number K of data sets. This is followed by K data sets, each of the following form:
The first line contains four integers n,m,p,y. n is the number of bus stops (2 ≤ n ≤ 100), m the number of seats on the bus (1 ≤ m ≤ 100), and p the number of passengers. 1 ≤ y ≤ p is your number as a passenger.
This is followed by a line with n − 1 integers, giving the time (in seconds) from station i to i + 1. The next line contains m non-negative integers, giving the proportion ai of the bandwidth that seat i commands.
This is followed by p lines, each describing one passenger j, by giving two integers, the station sj where the passenger gets on, and the station tj > sj where he gets off. The passengers will be sorted by non-decreasing start stations.
For each data set, output “Data Set x:” on a line by itself, where x is its number. Then, on a separate line, output the total bandwidth in megabytes you obtained, rounded to two decimals. Each data set should be followed by an empty line.
2 2 2 3 3 600 2 1 1 2 1 2 1 2 6 3 6 2 231 165 198 132 132 1 2 3 1 2 1 5 1 3 3 5 4 6 4 6
Data Set 1: 0.00 Data Set 2: 310.20