0129. Nearest Approximation

Имя входного файла:	nearest.in
Имя выходного файла:	nearest.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

You are given N integer numbers. Your task is to insert only one plus or minus sign between any two adjacent of them so as to make the value of the resulting expression as close as possible to a given integer number A.

Input file

First line of the input file contains two integer numbers: N (1 ≤ N ≤ 10000) and A which cannot be greater than 10000 by an absolute value. N lines follow, each containing only one integer number X_i which does not exceed 10000 by an absolute value. Also it is guaranteed that the total sum of absolute values of all N numbers does not exceed 10000.

Output file

In the first line you are to output the value of the resulting function (% which has to be as close as possible to A). In the second line the optimal expression giving such a value must be displayed in the form X₁[+|-]X₂[+|-]…X_N-1[+|-]X_N.

Examples:

nearest.in	nearest.out
3 0 3 -2 1	0 3+-2-1

Источник: Petrozavodsk Summer 2003. Blitz Kontest, Monday, August 25
Автор: Andrew Lopatin, Nick Durov

Обсудить       Отправить решение



Версия для печати