Format a Table

Time limit5sMemory limit64 MB

Summary

Given a 3x3 table of cell text lengths and a total width w, split w into three column widths that minimize the sum of the three row heights.

Level: Hard8 of 10
Topics: Brute force, Math, Binary search
Solved: No attempts yet

Problem

Little Vadim has a homework assignment at school. He has to describe the characters of a famous literary work. Vadim finished the homework and wrote a report as a spreadsheet in his favorite text editor.

The spreadsheet is a table of size $3 \times 3$ . The text in the cell at row $i$ and column $j$ has length $a_{ij}$ . The total width of the table is $w$ characters. The editor lets you change the width of each column in any way. If the column widths are $x$ , $y$ , and $z$ , then $x+y+z=w$ . The height of row $i$ is $h_i = \max \left( \lceil a_{i1} / x \rceil, \lceil a_{i2} / y \rceil, \lceil a_{i3} / z \rceil \right)$ , and the total height of the table is $h = h_1 + h_2 + h_3$ .

Vadim noticed that changing the column widths changes the table height in an unpredictable way. He is a perfectionist, so he wants the total height to be as small as possible. Help Vadim find the optimal solution.

Input

The first line contains an integer $w$ ( $3 \le w \le 10^9$ ).

Each of the next three lines contains three integers. The $j$ -th number in the $i$ -th of these lines is $a_{ij}$ ( $1 \le a_{ij} \le 10^{12}$ ).

Output

In the first line, output the integer $h$ , the minimum possible height of the whole table.

In the second line, output three integers $x$ , $y$ , and $z$ , the column widths that give the optimal solution.

If there are several solutions, output any of them.

Hint

The following table matches the data from the first sample.


lawfu``lgood	neutra``lgood	chaoti``cgood
lawfu``lneut``ral	neutra``l	chaoti``cneutr``al
lawfu``levil	neutra``levil	chaoti``cevil

Examples1

Example 1
Input
```
17
10 11 11
13 7 14
10 11 11
```
Expected output
```
7
5 6 6
```