Натискання кнопок#8338
Ви нещодавно придбали нову мікрохвильову піч і помітили, що вона має багато кнопок для швидкого встановлення часу роботи. Є кнопки як для збільшення, так і для зменшення часу. Ви прагнете бути максимально ефективними у введенні часу приготування: ваша мета — мінімізувати кількість натискань кнопок.
Мікрохвильова піч може працювати від секунд до години. Якщо натискання кнопки призведе до встановлення часу менше секунд, час приготування буде секунд. Якщо натискання кнопки призведе до часу більше години, час приготування буде година. Спочатку мікрохвильовка налаштована на секунд. Завжди є кнопка, яка додає принаймні секунду до часу приготування.
Враховуючи доступні кнопки на мікрохвильовій печі для введення часу приготування, визначте мінімальну кількість натискань кнопок, необхідних для встановлення мікрохвильової печі на певний час. Якщо точно встановити бажаний час не вдається, визначте найменший можливий час приготування, що перевищує ціль, і мінімальну кількість натискань кнопок, необхідних для цього часу. Мікрохвильова піч не дозволяє змінювати час приготування після його початку.
Перший рядок містить кількість тестів t~(t \le 100). Далі для кожного тесту:
один рядок з двома цілими числами і t~(1 \le n \le 16, 0 \le t \le 3600): кількість кнопок, доступних для зміни часу приготування, і бажаний час приготування в секундах, відповідно.
один рядок з цілими числами b_i~(-3600 \le b_i \le 3600): кількість секунд, що додаються до часу приготування при натисканні кнопки .
Для кожного тесту:
один рядок з двома цілими числами: мінімальна кількість натискань кнопок, необхідних для досягнення потрібного часу приготування, і мінімальна кількість додаткових секунд, на які мікрохвильова піч повинна працювати, відповідно.
Приклад 1