Переміщення#2534
Емма та Ерік переїжджають до свого нового будинку після повернення з медового місяця. На щастя, у них є кілька друзів, які допомагають з переїздом. Для перевезення меблів у них є лише два компактні автомобілі, що ускладнює справу. Оскільки меблі не вміщуються в автомобілях, Ерік планує розмістити їх на дахах машин. Проте кожен автомобіль може витримати лише певну вагу на даху, тому їм доведеться здійснити кілька поїздок, щоб перевезти все. Графік переїзду такий:
На старому місці вони завантажують меблі на обидва автомобілі.
Потім вони їдуть до нового місця на обох автомобілях і заносять меблі до будинку.
Нарешті, всі разом повертаються до старого місця. Процес повторюється, поки всі меблі не будуть перевезені до нового будинку.
Зверніть увагу, що група завжди залишається разом, щоб переїзд був веселим і ніхто не почувався самотнім. Оскільки відстань між будинками велика, Ерік хоче зробити якомога менше поїздок.
Відомі ваги w_i кожного предмета меблів і місткості C_1 і C_2 двох автомобілів. Скільки поїздок до нового будинку потрібно зробити, щоб перевезти всі меблі? Якщо автомобіль має місткість , сума ваг всіх меблів, які він перевозить за одну поїздку, не може перевищувати .
Перший рядок містить кількість сценаріїв. Кожен сценарій складається з одного рядка з трьома числами , C_1 та C_2. C_1 і C_2 — місткості автомобілів (1 \leq C_i \leq 100), а — кількість предметів меблів (1 \leq n \leq 10). Наступний рядок містить цілих чисел w_1, w_2, \ldots, w_n, ваги меблів (1 \leq w_i \leq 100). Гарантується, що кожен предмет меблів можна перевезти хоча б одним із двох автомобілів.
Для кожного сценарію почніть вивід з рядка "Scenario #i:", де — номер сценарію, починаючи з . Потім виведіть один рядок з кількістю поїздок до нового будинку, необхідних для перевезення всіх меблів. Завершіть кожний сценарій порожнім рядком.
Приклад 1