Мастер-класс, начальная ступень, весна 2014

Задача C. Отрезки с наложением ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	Г. Гренкин	Ограничение времени:	2 сек
Входной файл:	input.txt	Ограничение памяти:	64 Мб
Выходной файл:	output.txt

Условие

Дано N отрезков с длинами w₁, …, w_N. Требуется расположить их на интервале числовой оси [0, L] так, чтобы они покрыли этот интервал без пропусков и не выходили за его границы.

Необходимо использовать все отрезки. Отрезки можно накладывать друг на друга.

Формат входного файла

Первая строка входного файла содержит целые числа N и L.

Вторая строка содержит N целых чисел w₁ w₂… w_N.

Формат выходного файла

Выходной файл должен содержать N целых чисел x₁ x₂… x_N — координаты левых концов отрезков.

Если решения не существует, то выходной файл должен содержать единственное число  − 1. Если существует несколько решений, вывести любое из них.

Ограничения

1 ≤ N ≤ 1000, 1 ≤ L ≤ 10000, 1 ≤ w_i ≤ 10000.

Примеры тестов

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`2 3 2 2`	`0 1`