405644: GYM102020 K K-pop

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:

• A sequence $$$O \Rightarrow D$$$ is a sequence of flights that starts on the city $$$O$$$ and ends on the city $$$D$$$, representing, then, a way of Clodes getting from his city to the event
• A sequence $$$O \Rightarrow D$$$ with $$$X$$$ seats means that every flight taken on this sequence must have $$$A_i \ge X$$$ available seats
• The cost of a sequence is the sum of prices of all flights used on it
• The cheapest sequence $$$O \Rightarrow D$$$ with $$$X$$$ seats is the one with minimum cost
• The number $$$V$$$ of friends Clodes will bring with him is the maximum prime number $$$V$$$, such that there exists a sequence $$$O \Rightarrow D$$$ with $$$V$$$ seats. In case there is no sequence that fulfills those requirements, then Clodes will be very sad and $$$V$$$ will be $$$0$$$. But he desperately wants to go to this event, therefore, if there is no answer to his problem, but exists a sequence $$$O \Rightarrow D$$$ with $$$1$$$ seat, Clodes will go by himself (i.e., $$$V$$$ will be equal to $$$1$$$), even though $$$1$$$ is not a prime number.
• The total value $$$T$$$ his grandma will spend is going to be $$$0$$$, if Clodes can't make it to the event, or the cost of the cheapest sequence $$$O \Rightarrow D$$$ with $$$V$$$ seats multiplied by $$$V$$$, since she's going to pay for all of his friends too.

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