Все проектировщики компьютерных игр используют понятие искусственного интелекта, чтобы сделать свои программы более умными и естественными. Проектировщики новой стратегической игры, Сверхестественной Идентичности (СИ), столкнулись с похожими проблемами при проектировании своей игры, особенно при проектировании компьютерных игроков. В таких играх каждый игрок (компьютер или человек-игрок) имеет некоторые ресурсы, такие как золото, дерево, ископаемые. Игрок в любое время решает, когда и где тратить эти ресурсы. Для простоты, мы допустим, что в СИ есть только один тип ресурсов, то есть золото. Одной из главных сфер для их расходов есть военная. В СИ есть некоторые встроенные виды военных единиц. Каждый тип имеет связанные с ним цену, еду и силу.

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

Задача состоит в том, чтобы помочь проектировщикам СИ запрограммировать такого компьютерного игрока, который (компьютерный игрок) максимизировал свою военную силу, когда он имеет конкретное количество денег, еды и фиксированное количество выбора.

Например, если мы имеем 300 единиц золота, наши запасы еды сосотавляют 20 и количество единиц вибора составляет 3, то мы должны приобрести точно 3 единицы таких новобранцев, чтобы на их содержание необходимо было не более чем 20 единиц еды и их общая стоимость не должна превышать 300, а полная сила (сумма сил солдат) должна быть максимальной. Отметим, что один тип солдат может быть выбран более одного раза.

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

Первая строка содержит единственное целое число – количество тестовых случаев. Далее идут данные для каждого из тестовых случаев. Каждый тестовый случай начинается з одной строки, содержащей четыре целых числа. Первое число, М (0 ≤ М ≤ 5000), - текущее доступное золото (деньги), второе - F (0 ≤ F ≤ 500), доступный на данный момент запас продовольствия, третье - U, количество выборов новобранцев, которые должны быть точно приобретены, и четвертое число – T количество доступных типов новобранцев (1 ≤ U, T ≤ 10). Следующие T строк содержат данные для типов новобранцев, одна строка для каждого типа. Каждая из этих строк содержит три целых числа: цена новобранца (от 1 до 100), количество необходимого продовольствия (от 1 до 20) и силу новобранца (не отрицательное целое число). Предполагается, что нет двух одинаковых типов новобранцев.

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

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