Золото, їжа і сила

Всі проектувальники комп'ютерних ігор використовують поняття штучного інтелекту, щоб зробити свої програми більш розумними та природними. Проектувальники нової стратегічної гри, Надприродної Ідентичності (НІ), зіткнулися з подібними потребами при проектуванні їх програмного забезпечення, особливо при проектуванні комп'ютерних гравців. У таких іграх кожен гравець (комп'ютер або людина-гравець) має деякі ресурси такі як золото, деревина, руда. Гравець у будь-який час вирішує, коли і де витрачати ці ресурси. Для простоти, ми припускаємо, що в НІ є тільки один тип ресурсу, тобто золото. Однією з найголовніших сфер для витрачання грошей є військова. У НІ є деякі вбудовані види військових одиниць. Кожен тип має зв'язані ціну, їжу і силу.

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

Проблема полягає в тому, щоб допомогти проектувальникам НІ запрограмувати такого комп'ютерного гравця, який би (комп'ютерний гравець) максимізував свою армійську силу, коли він має конкретну кількість грошей, їжі та фіксовану кількість виборів.

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

Вхідні дані

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

Вхідні дані

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