Le petit Vadim a un devoir à l'école : il doit décrire les personnages d'une œuvre littéraire célèbre. Vadim a terminé son devoir avec succès et a rédigé un rapport sous forme de feuille de calcul dans son éditeur de texte préféré.

La feuille de calcul a la structure suivante. Il s'agit d'un tableau de taille $3 \times 3$. À l'intersection de la $i$-ième ligne et de la $j$-ième colonne est placé un texte de longueur $a_{ij}$. La largeur totale du tableau est de $w$ symboles. L'éditeur de texte permet de modifier la largeur de chaque colonne de manière arbitraire. Soient $x, y$ et $z$ les largeurs des colonnes, avec $x + y + z = w$. Alors, la hauteur de la $i$-ième ligne est $h_i = \max(\lceil a_{i1}/x \rceil, \lceil a_{i2}/y \rceil, \lceil a_{i3}/z \rceil)$, et la hauteur totale du tableau est $h = h_1 + h_2 + h_3$.

Vadim a remarqué que la modification de la largeur des colonnes change la hauteur totale du tableau de manière imprévisible. Vadim est perfectionniste et il souhaite modifier la largeur des colonnes de telle sorte que la hauteur totale du tableau soit minimale.

Aidez Vadim à trouver la solution optimale.

Entrée

La première ligne contient l'entier $w$ ($3 \le w \le 10^9$).

Les trois lignes suivantes contiennent chacune trois entiers. Le $j$-ième nombre de la $i$-ième ligne est l'entier $a_{ij}$ ($1 \le a_{ij} \le 10^{12}$).

Sortie

Sur la première ligne, affichez l'entier $h$ — la hauteur minimale possible de l'ensemble du tableau.

Sur la deuxième ligne, affichez trois entiers $x, y$ et $z$ — les largeurs des colonnes qui permettent d'obtenir la solution optimale.

S'il existe plusieurs solutions, affichez l'une d'entre elles.

Exemples

Entrée 1

17
10 11 11
13 7 14
10 11 11

Sortie 1

7
5 6 6

Remarque

Le tableau suivant correspond aux données du premier exemple :

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