Формат выходного файла. Формат выходного файла. F. Задача о рюкзаке. Формат входного файла. Формат выходного файла. Примеры

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

Ввод из файла input. txt. В первой строке находятся числа E и F, во второй - число N, в следующих N строках - по два числа, P_i и W_i.

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

Вывод в файл output. txt. Выводятся два числа через пробел - минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, - вывести " This is impossible. ".
Примеры

input. txt	output. txt
1000 1100 1 1 5 2	100 250
1000 1010 6 3 2 2	10 16
1000 2000 10 3	This is impossible.

F. Задача о рюкзаке

Дано n предметов, каждый из которых характеризуется весом w_i и полезностью p_i. Необходимо выбрать некоторый набор этих предметов так, чтобы суммарный вес этого набора не превышал W, а суммарная полезность была максимальна.

Ваша задача состоит в том, чтобы написать программу, решающую задачу о рюкзаке.

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

Первая строка входного файла содержит натуральные числа n (1≤ n≤ 100) и W (1≤ W≤ 10⁹). Каждая из последующих n строк содержит описание одного предмета. Каждое описание состоит из двух чисел: w_i — веса предмета и p_i — его полезности (1≤ w_i, p_i≤ 10⁹).

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

В первой строке выходного файла выведите максимальную суммарную полезность. Во второй – номера предметов (в порядке следования в исходных данных), которые были использованы.

Примеры

input. txt	output. txt
2 10 10 100 9 80
5 100 80 1000 50 550 50 550 50 550 50 550	2 3
6 200 80 1000 50 550 50 550 50 550 50 550 100 1100	2 3 4 5