Задача о рюкзаке - 2

Одной из классических NP-полных задач является так называемая Задача о рюкзаке. Формулируется она следующим образом.

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

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

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

Содержательным, по Вашему мнению, тест является тогда и только тогда, когда все веса предметов различны и не меньше W_min, все стоимости предметов различны и не меньше C_min, в наборе, соответствующем правильному ответу, содержится не менее K_min элементов и, кроме того, вместе с этим набором существуют:

1. набор, дающий такую же стоимость, но содержащий больше предметов;

2. набор, дающий такую же стоимость, содержащий такое же число элементов, но лексикографически идущий позже правильного ответа.

Кроме этого, сумма всех весов и сумма всех стоимостей не должны превосходить 10¹⁸, так как младший брат еще слишком мал, чтобы реализовывать операции с длинными числами.

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

Входные данные

Входной файл INPUT.TXT содержит четыре числа: n, W_min, K_min и C_min (6 ≤ n ≤ 25, 1 ≤ W_min ≤ 10⁹, 1 ≤ C_min ≤ 10⁹, 1 ≤ K_min ≤ n−1). Гарантируется, что всегда существует хотя бы одно решение.

Выходные данные

В выходной файл OUTPUT.TXT в первую строку выведите числа n и W. Число W определяете Вы. Далее выведите n строк, в каждой 2 числа: w_i и c_i, разделенные пробелами. Полученный набор должен быть содержательным. При существовании нескольких таких наборов выведите любой.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!