小さなVadimは学校の宿題で、ある有名な文学作品の登場人物について記述しなければなりません。Vadimは宿題を無事に終え、お気に入りのテキストエディタでスプレッドシート形式のレポートを作成しました。

このスプレッドシートは $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$ となります。

Vadimは、列の幅を変えると表全体の高さが予測できない形で変化することに気づきました。完璧主義者のVadimは、表全体の高さが最小になるように列の幅を変更したいと考えています。

Vadimを助け、最適な解を見つけてください。

入力

1行目には整数 $w$ ($3 \le w \le 10^9$) が与えられます。

続く3行には、それぞれ3つの整数が与えられます。これらの行の $i$ 行目における $j$ 番目の数値は整数 $a_{ij}$ ($1 \le a_{ij} \le 10^{12}$) です。

出力

1行目に、表全体の最小の高さ $h$ を出力してください。

2行目に、最適な解となる列の幅 $x, y, z$ を出力してください。

複数の解が存在する場合は、そのうちのどれを出力しても構いません。

入出力例

入力 1

17
10 11 11
13 7 14
10 11 11

出力 1

7
5 6 6

注記

以下の表は、最初の入出力例のデータに対応しています。

最初の入出力例のデータに対応する表