## QCC P5 - Vaccine Delivery

View as PDF

Points: 12
Time limit: 2.0s
Python 8.0s
Memory limit: 256M
Python 512M

Author:
Problem types

Having developed a COVID-19 vaccine, CodeVax gives you one final assignment: Deliver the CodeVax vaccine to cities around the world.

More specifically, the planet Earth has a radius of and a centre at . There are cities numbered from to on Earth's surface. Additionally, there are bidirectional roads connecting cities together. The distance between two cities a b is defined as the shortest distance between the two points by travelling on the surface of planet Earth. Each city has active COVID-19 cases. Furthermore, of the cities, only of them have airports. You start in city and can travel along roads at unit per second.

Wanting to help the most people, you decide you will deliver the CodeVax vaccines to the city with the highest number of active COVID-19 cases you can reach, while still getting to an airport strictly before seconds. Output the number of active COVID-19 cases of such a city or -1 if you can't reach an airport under seconds.

#### Input Specification

The first line of input will contain the positive integers , , , , and .

The next line will contain integers, denoting which of the cities contain an airport to take you home.

The next lines will contain the integer and the numbers , , , the number of active COVID-19 case and the coordinates of the th city. The coordinates of each city will be rounded up to ten decimal places.

The next lines will contain two integers and , meaning there is a bidirectional road between cities and .

#### Output Specification

Output the number of active COVID-19 cases of the most infected city you can reach while reaching a city that has an airport. If you are unable to reach any airport strictly before seconds, print -1.

#### Constraints

You may visit any road and/or city multiple times. All are distinct. Not all roads are guaranteed to be distinct. It is guaranteed that the cities will lie on the Earth's surface to within an absolute error of less than .

#### Sample Input 1

3 3 3 7 2
2 3
0 -2.5000000000 0.0000000000 1.6583123952
1 1.5000000000 2.0000000000 1.6583123952
2 0.0000000000 0.0000000000 -3.0000000000
1 2
2 3
1 3

#### Sample Output 1

2

#### Explanation for Sample 1

You can travel directly to city and deliver the vaccines there in under seconds. From there, you can leave through the airport at city .

#### Sample Input 2

3 3 3 6 2
2 3
0 -2.5000000000 0.0000000000 1.6583123952
1 1.5000000000 2.0000000000 1.6583123952
2 0.0000000000 0.0000000000 -3.0000000000
1 2
2 3
1 3

#### Sample Output 2

1

#### Explanation for Sample 2

You cannot travel to city in under seconds. Therefore you must head to city , deliver the vaccines there, and leave through the airport at city .