SENIOR 2

Stacking Numbers

Input File: stackin.txt
Output File: stackout.txt
Time Limit: 2 seconds

It's raining outside, you're bored and you desperately need something to do. Staring at a pile of soft drink cans in the corner, you devise a game that could keep you entertained for hours.

This game is played on a pyramid of side length six. This pyramid contains 21 boxes as illustrated below. In each box you must place a single non-negative integer.

You may choose the six integers that are placed in the bottom row of the pyramid. Once this bottom row has been filled, you have rules that describe how to fill the remaining boxes from bottom to top. The integer that is placed in the very top box of the pyramid is your score. Your aim is to obtain the highest score possible.

Before you play the game you are given some positive integer b called the base. The rules for filling in the remaining boxes are as follows.

• For each box below the top row, you add the integers in the two boxes directly beneath it. If this sum is greater than or equal to the base b, you subtract b from this total so that the sum becomes strictly less than b.
• For the very top box, you simply multiply the integers in the two boxes directly beneath it.

A sample game is illustrated below, played with base b = 100. The left hand diagram shows six integers initially placed in the bottom row, and the right hand diagram shows the resulting pyramid with every box filled.

Examine the first box of the fourth row (61). This box simply contains the sum of the two integers beneath it: 33+28. On the other hand, consider the first box of the third row (49). The sum of the two integers beneath it is 61+88 = 149, which is larger than b. We thus subtract b = 100 from this total to obtain 49, which is placed within the box. The topmost box contains 9702, which is the product 99 x 98.

Note that every box aside from the topmost box contains an integer between 0 and b-1 inclusive. In particular, if the two integers beneath a box add to precisely b then that box is filled with the integer 0.

To make the game more interesting, you are given a small set of numbers from which the six integers in the bottom row must be chosen. No integer from this set may be used more than once in the bottom row. You must write a program that selects six integers from this set to place in the bottom row so that you obtain the highest score possible.

Input

The input file will consist of three lines. The first line will contain the base b with which the game is played. You are guaranteed that 1 <= b <= 32,768.

The second line will contain an integer s representing the number of integers in your set from which the bottom row must be chosen. You are guaranteed that 6 <= s <= 32.

The third line will contain the entire list of s integers from which the bottom row of the pyramid must be chosen. Each of these integers will be between 0 and b-1 inclusive. These integers will be separated by spaces, and no two of these integers will be equal.

Output

The output must consist of precisely two lines. The first line must contain a single integer representing the highest possible score.

The second line must contain six integers that can be placed in the bottom row of the pyramid to obtain this highest possible score. The six integers should be written from left to right as they appear in the bottom row, and should be separated by spaces.

If more than one solution exists then you should only output one of these solutions. Any of these solutions will suffice.

Sample Input 1

100
7
1 2 3 4 5 6 7

Sample Output 1

8100
2 5 6 7 4 3

Sample Input 2

100
8
7 12 15 21 35 49 53 67

Sample Output 2

9702
12 21 7 53 49 35

Scoring

The score for each input file will be 100% if a correct solution is written to the output file and 0% otherwise.

Copyright © 2003 Australian Mathematics Trust