Маленькому Вадиму задали домашнее задание в школе: он должен описать персонажей одного известного литературного произведения. Вадим успешно справился с заданием и оформил отчет в виде таблицы в своем любимом текстовом редакторе.

Таблица имеет следующую структуру: это таблица размера $3 \times 3$. На пересечении $i$-й строки и $j$-го столбца расположен текст длиной $a_{ij}$. Общая ширина таблицы составляет $w$ символов. Текстовый редактор позволяет произвольно изменять ширину каждого столбца. Пусть ширины столбцов равны $x, y$ и $z$, при этом $x + y + z = w$. Тогда высота $i$-й строки равна $h_i = \max(\lceil a_{i1}/x \rceil, \lceil a_{i2}/y \rceil, \lceil a_{i3}/z \rceil)$, а общая высота таблицы равна $h = h_1 + h_2 + h_3$.

Вадим заметил, что изменение ширины столбцов непредсказуемым образом меняет высоту всей таблицы. Вадим — перфекционист, и он хочет изменить ширину столбцов так, чтобы общая высота таблицы была минимальной.

Помогите Вадиму найти оптимальное решение.

Входные данные

Первая строка содержит целое число $w$ ($3 \le w \le 10^9$).

Следующие три строки содержат по три целых числа каждая. $j$-е число в $i$-й из этих строк — это целое число $a_{ij}$ ($1 \le a_{ij} \le 10^{12}$).

Выходные данные

В первой строке выведите целое число $h$ — минимально возможную высоту всей таблицы.

Во второй строке выведите три целых числа $x, y$ и $z$ — ширины столбцов, при которых достигается оптимальное решение.

Если существует несколько решений, выведите любое из них.

Примеры

Входные данные 1

17
10 11 11
13 7 14
10 11 11

Выходные данные 1

7
5 6 6

Примечание

Следующая таблица соответствует данным из первого примера:

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