Description

A city holds a winter around-the-city $25\rm km$ marathon relay. Each team has $5$ participants. Each participant runs exactly once, with each leg being at least $1\rm km$ and at most $10\rm km$, and the distance each runner covers must be an integer, i.e., handoffs occur at whole-kilometer marks.

Coach Liu, as the coach of the school team, carefully selected $5$ endurance runners and conducted training and tests to obtain the time each of the $5$ runners needs to run continuously for $1\rm km$, $2\rm km$, …, $10\rm km$. He now needs to make a reasonable arrangement so that each runner runs a suitable number of kilometers, minimizing the total time to finish $25\rm km$. Given the athletes’ abilities, this minimal time is unique, but the arrangement plan may not be unique.

Based on the test results and typical athletes’ performance, running $1\rm km$ continuously is faster than running $2\rm km$, running $2\rm km$ is faster than running $3\rm km$, and so on. In other words, the longer the continuous distance, the slower the speed. There can be special cases where the speed does not slow down, but it can never get faster.

Input Format

$5$ lines of data, corresponding to the test data of athletes $1$ to $5$. Each line contains $10$ integers, representing the time it takes that athlete to run continuously for $1\rm km$, $2\rm km$, …, $10\rm km$. Each time is a positive integer not exceeding $10^7$.

Output Format

Two lines. The first line is the minimal total time. The second line contains five integers, which are the consecutive kilometers covered by athletes $1$ to $5$.

333 700 1200 1710 2240 2770 3345 3956 4778 5899 
300 610 960 1370 1800 2712 3734 4834 5998 7682
298 612 990 1540 2109 2896 3790 4747 5996 7654
289 577 890 1381 1976 2734 3876 5378 6890 9876
312 633 995 1407 1845 2634 3636 4812 5999 8123

9905
6 5 5 4 5

Hint

@Jomoo provided the corrected testdata.

Translated by ChatGPT 5