Boxes

PROBLEM

Santa Claus has found a nice new sleigh from the sleigh shop. Santa’s old sleigh and the new sleigh have equal amount of room for the magic boxes Santa Claus uses to carry Christmas presents. For comparing sleighs, Santa’s elves have carried a set of boxes to the shop. Each box has an integer volume. Santa Claus wants to compare the flying properties with sleighs packed so that the sums of the box volumes in the sleighs are as close as possible to a desired value.

Suppose that the desired sum of box volumes for both sleighs is D, and that a sleigh is packed so that the sum of the volumes in the sleigh is S. If S<=D, then the filling of that sleigh is S, and otherwise the filling is max(0,2D-S). Given volumes of the available boxes and the required filling of the sleighs, you are to find such a placement of boxes for the two sleighs that the sum of the fillings of the two sleighs is as large as possible.

INPUT

The input file names are boxes.inI, where I is one of characters 1,2,3,4, or 5. The first line of the input file contains one integer: the number of boxes N, 1<= N <=17. The second line contains the desired sum of box volumes D, which is the same for both sleighs. For D it holds that 1<=D<=100 000 000. The third line contains N integers w1, w2,...,wN,: the volumes of the N boxes. For each wi we have
1<=wi<=50 000 000 (1<= i <=n).

OUTPUT

The first line of the output file contains the string

#FILE boxes I

where I is the number of the input file respective to this output file. The second line contains one integer F: the sum of the fillings of the two sleighs. Then follow N lines, which describe the placement of the boxes as follows. On each of these lines there are two integers, W and K, where W is the size of one of the boxes (each box must appear in output), and K is the sleigh number of the sleigh for that box. Use sleigh numbers 1 and 2 for the sleighs and 0 if the box should not be placed in either of the sleighs.

EXAMPLE INPUTS AND OUTPUTS

To make a difference between the example and real inputs, we use input number 0 here.

boxes.in0
5
11
5 6 7 8 9

 

An output file to be submitted
#FILE boxes 0
20
7 0
9 2
8 0
5 1
6 1