XGN have watched the famous anime Spice and Wolf and now as usual, he will propose a problem.
In the country, there are N cities and M bidirectional roads. Each road connects two city and has a dangerous point Di. Each city has three properties: Pi - the profit, Fi - the deliciousness of the food there and Gi - the number of attractions in the city.
Now Lawrence, Horo and Nora are at city 1. Before the trip, Lawrence will give Nora X coins, which will be determined by you. This will make all roads with dangerous points less than or equal to X be available for passing.
Their journey will last for T days. In each day, they will first move to an adjacent city. There Lawrence will do some business and get Pi coins. The way they determine which city to go will follow these rules:
Assume they are at city x and all adjacent cities are in adj
Horo will first choose an adjacent city i randomly with the probability
Then Nora will choose an adjacent city j randomly with the probability
Then among city i and j, they will go to the one with higher profit.
For example, if the adjacent cities have [{P,F,G}]=[{1,2,3},{2,3,4},{5,6,7}], then a possible process is:
Horo chose city 1
Nora chose city 3
Lawrence decided to go to city 3 because it had higher profit
Possibility of this scene:
What’s the maximum expected profit after day T when the initial X is optimal? Please print the profit and the initial X.
Have you ever played Danganronpa? It’s a game which allows you to cut through others words by exposing lies. Our adorable swordsman Ookami decides to try it too!
There are N words Ookami needs to cut. They will appear in a plane as rectangles. The i-th one will appear at second , with its left-up corner at and right-down corner at . The left-up corner will move to and its right-down corner will move to linearly and smoothly in seconds. It will also have a health of