UFPE Starters Final Try-Outs 2019 |
---|
Finished |
Clodes is a student that is crazy about K-pop like no other person in the world. He has a grandma who loves him a lot and wishes to reward him for his outstanding grades and performance on his studies. To do so, his grandma decided to give him a gift: she will pay for him and his friends to attend a K-pop event, that is going to happen in another city.
Clodes, then, while planning his trip, was looking through a total of $$$N$$$ different cities, when he found $$$M$$$ available flights connecting two cities, where the $$$i$$$-th of them leaves from city $$$u_i$$$, lands at city $$$v_i$$$, costs $$$P_i$$$ taokeis (the currency of Clodes' country) and has $$$A_i$$$ available seats on the plane. Clodes doesn't want to be apart of his friends, therefore, all of his friends must go on the same flight as him. Therefore, Clodes seeks a sequence of flights starting at $$$O$$$, the city he lives in, and ends at $$$D$$$, the city where the K-pop event wil happen. Every flight of this sequence must have room for all his friends.
There is one more thing. Clodes loves number theory. Even more than his friends do. Because of that, he decided that he wants to take a prime number of friends on the trip with him, including himself on that count, because Clodes considers himself his friend.
But life is not easy, specially for Clodes, since he chose to do his graduation on Computer Engineering, instead of Computer Science. He is full of exams this week and needs to study, thus, he doesn't have any more time available to plan his trip and wants your help. He wants you to calculate the minimum amount of money his grandma needs to spend in order to get him and his friends to the event, where the total number of people (Clodes and his friends) is the highest prime possible.
To help you with your difficult task, Clodes decided to formalize the problem before going to study:
Warning: large input, it is recommended to use fast I/O.
The first line of input contains four integers $$$N$$$, $$$M$$$, $$$O$$$ and $$$D$$$ ($$$2 \le N \le 10^5$$$, $$$0 \le m \le 5 \cdot 10^5$$$, $$$1 \le O, D \le N$$$, $$$O \ne D$$$), being, respectively: the number of cities, the number of available flights, the city Clodes lives in and the city on which the event will hapen.
Then, $$$M$$$ lines follow, where the $$$i$$$-th of them contains four integers $$$u_i$$$, $$$v_i$$$, $$$A_i$$$, $$$P_i$$$ ($$$1 \le u_i, v_i \le N$$$, $$$u_i \ne v_i$$$, $$$1 \le A_i, P_i \le 5 \cdot 10^6$$$), representing, respectively, the city of departure, the city of arrival, the number of available seats and the cost of the ticket (in Taokeis) of the $$$i$$$-th flight.
Your program must output two integers: the number $$$V$$$ of friends Clodes will take with him on his trip, and the total value $$$T$$$ his grandma will pay so that this trip can happen.
4 5 1 4 1 4 4 6 1 3 7 1 3 4 2 2 1 2 3 2 2 4 5 3
3 15
4 2 1 4 1 2 3 4 3 4 7 3
0 0
Name |
---|