The Monastery of Jerónimos must be saved from the rising waters of the River Tagus. As with Abu Simbel, in Egypt, this is a massive removal project: the monastery will be cut into small blocks, to be carried in big lorries to their new destination, where the building will be reassembled.
To prevent loss, blocks will be numbered in sequence (1,2,...,i,...) as they are being cut out of the monastery, and each lorry will carry a contiguous sub-sequence of blocks (e.g., from block 1 to block 5 or from block 6 to block 6). All lorries can carry the same maximum weight, called the lorry capacity. Furthermore, every block has a weight which does not exceed the lorry capacity, and the sum of the block weights carried by one lorry cannot be greater than the lorry capacity. This problem deals with the distribution of the blocks among lorries.
In a block distribution all blocks are distributed among lorries. The aim is to minimize the number of lorries needed to carry all blocks, and to balance their loads as evenly as possible, so as not to cause unnecessary wear and tear of some vehicles. To this purpose we define:
Write a program that, given the lorry capacity and a sequence of block weights, computes the number of lorries and the balance-factor of an optimal block distribution.
For each test case,
the balance-factor of an optimal block distribution
does not exceed 231 - 1.
Input
The first line contains an integer C (1 <= C <= 2000), which represents the lorry capacity. The second line contains an integer n (1 <= n <= 100000), which is the length of the sequence of block weights.
Each of the following n lines contains
an integer wi (1 <= wi <= C)
which denotes the weight of the ith block.
Output
The first line contains the number of lorries and
the second line contains the balance-factor of an optimal block distribution.
Sample Input
6 5 1 2 3 1 1
2 10