小 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 找到最优解。

输入格式

第一行包含一个整数 $w$ ($3 \le w \le 10^9$)。

接下来的三行，每行包含三个整数。第 $i$ 行的第 $j$ 个数字是整数 $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

说明

下表对应样例中的数据：