Witty must choose the order in which the cities should be visited, to maximize the profit. Some cities are connected by bidirectional roads. Although musical equipment and performers move from city to city by air, roads play important role in a way musical fans visit musicals and exchange information about
To estimate the profit Witty has gathered information about musical fans in all cities. He divided them to three categories.
Having all this information, as well as the information about all other musicals that will be staged during next weeks, help Witty to choose the order in which the cities should be visited by the tour to maximize the expected number of fans that would come to see his musical.
- Ordinary musical fans go to one musical per week. They only attend musicals that are staged in their city. When there are several musicals possible, they choose the one which they have most information about. The amount of information depends on the number of neighboring cities that were already visited by the musical. Two cities are neighboring if they are connected by a road. If there are several musicals they have equal information about they go to a random one.
- Crazy musical fans go to one musical every day. When there are several musicals in the city, theygo to a random one.
- Finally, musical maniacs go to one musical every day, choosing one from the city they live in and all neighboring cities. When there are several possible musicals to choose from, they choose a random one.
The first line of the input file contains three integer numbers: n, m and k — the number of cities, roads, and other musicals (1 ≤ n ≤ 10, 0 ≤ m, 0 ≤ k ≤ 10). The following n lines describe cities. Each city is described with three integer numbers not exceeding 106 — the number of ordinary musical fans, the number of crazy musical fans, and the number of musical maniacs.
The following m lines describe roads, each road is described by two integer numbers — the numbers of cities it connects. No two cities are connected by more than one road, no road connects a city to itself. The following k lines give the time table of other musicals. Each musical is described with n numbers, the i-th of these numbers is the number of the city where the musical will be staged on the i-th week, or 0 if the musical will be on vacation that week. Note that unlike Witty’s musical, other musicals may perform in the same city for more than once.
Print the maximal possible expected amount of attendants of Witty’s musical at the first line of the output file. Your answer must be accurate up to 10−6.
The second line must contain the permutation of n numbers — the order in which the cities must be visited to maximize the expected attendance.
3 2 1
100 10 20
20 50 30
10 40 30
2 3 1
In this example, there are 555 people expected to come see musical on the first week — 100 ordinary fans, 10 crazy fans every day for a total of 70, 20=2 = 10 maniacs from the first city, 30=2 = 15 maniacs from the second city, and 30 maniacs from the third city every day for a total of (10 + 15 + 30) · 7 = 385 maniacs, and therefore 100 + 70 + 385 = 555 people on the first week.
On the second week the musical is expected to be visited by 20 + 50 · 7 + (20=2 + 30) · 7 = 650 people, and on the third week by 10 + 40 · 7 + (20=2 + 30=2) · 7 = 465 people, for a total of 1670 expected people on all three weeks.
Andrew Stankevich Contest 21
No tag edit access