Задача A. Перетягивание канатов ≡

Условие

На уроке физкультуры дети решили поиграть в перетягивание канатов. Чтобы игра была интересной, им нужно разделиться на две команды, как можно меньше различающиеся по силе. Кроме того, одного школьника следует назначить судьей, который будет следить за тем, чтобы поединок проходил честно.

Дети обратились к самому умному ученику в классе, Васе, с просьбой поделить их на две команды и выбрать судью.

Вася измерил силу каждого ученика, и решил, что сила команды будет рассчитываться как сумма величин силы её участников.

Требуется по данным значениям силы каждого из учеников найти такое разделение на две команды и судью, при котором абсолютная величина разности сил команд будет наименьшей.

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

Входной файла содержит целое число N — количество учеников, за которыми следуют N целых чисел a_i — силовые показатели каждого ученика.

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

Выходной файл должен содержать единственное число — наименьшую возможную абсолютную величину разницы сил получившихся команд.

Ограничения

3 ≤ N ≤ 30.

0 ≤ a_i ≤ 10⁷.

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

3
1 2 3
    

1

3
1 10 10
    

0

Задача B. Сокровища ≡

Условие

Дочь короля Флатландии собирается выйти за прекрасного принца. Принц хочет подарить принцессе сокровища, но он не уверен какие именно бриллианты из своей коллекции выбрать. В коллекции принца n бриллиантов, каждый характеризуется весом w_i и стоимостью v_i. Принц хочет подарить наиболее дорогие бриллианты, однако король умен и не примет бриллиантов суммарного веса больше R. С другой стороны, принц будет считать себя жадным всю оставшуюся жизнь, если подарит бриллиантов суммарным весом меньше L. Помогите принцу выбрать набор бриллиантов наибольшей суммарной стоимости, чтобы суммарный вес был в отрезке [L,R].

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

Первая строка содержит число n (1 ≤ n ≤ 32), L и R (0 ≤ L ≤ R ≤ 10¹⁸). Следующие n строк описывают бриллианты и содержат по два числа "--- вес и стоимость соответсвующего бриллианта (1 ≤ w_i, v_i ≤ 10¹⁵).

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

Первая строка вывода должна содержать k "--- количество бриллиантов, которые нужно подарить королю. Вторая строка должна содержать номера даримых бриллиантов. Бриллианты нумеруются от 1 до n в порядке появление во входных данных. Если составить подарок королю невозможно, то выведите 0 в первой строке вывода.

Ограничения

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

3 6 8
3 10
7 3
8 2

1
2