CD#1266

CD

1 second

122.812 megabytes

Very easy

You have a long car journey ahead. You have a tape recorder, but unfortunately your favorite music is only on CDs. In order to listen to it in the car, you need to record it onto a tape. You have a tape of $N$ minutes in length. How should you select tracks from the CD to make the best use of the tape's capacity, minimizing the unused space?

Assumptions:

The number of tracks on the CD does not exceed $100$ .
No track is longer than $N$ minutes.
The length of each track is an integer.
$N$ is also an integer ( $0 \leq N \leq 200$ 0 \leq N \leq 200).

The program should find a set of tracks that fills the tape as much as possible and print the chosen track durations in the same order as they appear on the CD.

Input

The input consists of multiple lines. Each line contains the value $N$ , followed by the number of tracks, then the durations of each track. All values are separated by spaces. For example, in the first line of the sample data: $N = 5$ N = 5, number of tracks $s = 3$ s = 3, first track lasts $1$ minute, second $3$ minutes, and the last $4$ minutes.

Output

Output the durations of the selected tracks in the order they appear on the CD on a single line. Then, on the next line, output the string sum: and the sum of their durations.

Examples

Example 1

Loading

0 \leq N \leq 200

N = 5

s = 3