어린 바딤은 학교 숙제로 유명한 문학 작품의 등장인물들을 설명해야 합니다. 바딤은 숙제를 성공적으로 마치고 자신이 가장 좋아하는 텍스트 편집기에서 스프레드시트 형태의 보고서를 작성했습니다.

이 스프레드시트는 $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$)가 주어집니다.

이어지는 세 줄에는 각각 세 개의 정수가 주어집니다. 이 줄들 중 $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

참고

다음 표는 첫 번째 예제의 데이터를 나타냅니다:

첫 번째 예제의 데이터를 나타내는 표