In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
You are visiting a park which has islands. From each island , exactly one bridge was constructed. The length of that bridge is denoted by . The total number of bridges in the park is . Although each bridge was built from one island to another, now every bridge can be traversed in both directions. Also, for each pair of islands, there is a unique ferry that travels back and forth between them.
Since you like walking better than riding ferries, you want to maximize the sum of the lengths of the bridges you cross, subject to the constraints below.
Note that you do not have to visit all the islands, and it may be impossible to cross all the bridges.
Write a program that, given the bridges along with their lengths, computes the maximum distance you can walk over the bridges obeying the rules described above.
- The number of islands in the park.
- The length of bridge .
Your program must read from the standard input the following data:
Your program must write to the standard output a single line containing one integer, the maximum possible walking distance.
NOTE 1: For some of the test cases the answer will not fit in a 32-bit integer, you might need int64 in Pascal or long long w C/C++ to score full points on this problem.
NOTE 2: When running Pascal programs in the contest environment, it is significantly slower to read in 64-bit data types than 32-bit data types from standard input even when the values being read in fit in 32 bits. We recommend that you read the input data into 32-bit data types.
For some cases worth 40 points, will not exceed .
For the input data:
7 3 8 7 2 4 2 1 4 1 9 3 4 2 3
the correct result is:
The bridges in the sample are (1-3), (2-7), (3-4), (4-1), (5-1), (6-3) and (7-2). Note that there are two different bridges connecting islands 2 and 7.
One way how you can achieve maximum walking distance follows:
The only island that was not visited is island 4. Note that at the end of the trip described above you can not visit this island any more. More precisely: