Однією з класичних NP-повних задач є так звана Задача про рюкзак. Формулюється вона наступним чином.

Задано n предметів, кожний з яких характеризується масою wi і корисністю pi. Необхідно вибрати деякий набір цих предметів так, щоб сумарна маса цього набору не перевищувала w, а сумарна корисність була максимальна.

Вхідні дані

Перший рядок містить натуральні числа n (1 ≤ n ≤ 20) і w (1 ≤ w ≤ 109). Далі йде n рядків по два числа: wi - маса і-го предмету та його корисність pi (1 ≤ wi, pi ≤ 109).

Вихідні дані

В першому рядку виведіть кількість вибраних предметів та їх сумарну корисність. В наступному рядку виведіть їх номери у порядку зростання (предмети нумеруються з одиниці в порядку, в якому вони задані на вході).

Якщо знайдених набрів декілька, виберіть той, в якому найменша кількість предметів. Якщо ж після цього відповідь неоднозначна, виберіть той набір, в якому перший предмет має найменший можливий номер, з усіх таких варіантів виберіть той, в якого другий предмет має найменший можливий номер і так далі.