Футбольный клуб
Сучасні футбольні клуби мають у своїй структурі велику кількість футболістів, проте на конкретний матч у складі команди можут вийти лише 11 гравців. При цьому один з них (воратар) стає на захист воріт і має право грати руками у своєму штрафному майданчику. Інші ж гравці також мають свої завдання і позиції на полі. Так захсники розміщуються в основному на своїй половині поля, їх завдання – протидіяти нападаючим гравцям команди-суперника. Напівзахисники діють у середині поля, допомогаючи захисникам або нападникам у залежності від ігрової ситуації. І нарешті нападникик розміщуються переважно на половині поля суперника і намагаються забити гол у чужі ворота.
У дійсності ж, кожен гравець може діяти давільній позиції, проте при цьому на одній позиції його корисність буде більшою, ніж на іншій. Це залежить, зокрема, від досвіду гри на відповідній позиції, набраній ним на даний момент ігрової форми та інших факторів. Кількість гравців на кожній позиції, крім воротарської, може бути якою завгодно, проте вона повинна вкладатись у одну з прийнятих тактичних схем.
Ви – головний тренер футбольного клубу ACM Ilan. У вашому розпорядженні N гравців, для кожного з яких відома його ефективність на кожній позиції. Є також K тактичних схем, за якими можуть розподілятись польові гравці вашої команди.
Напишіть програму, яка визначає найбільш вдалу тактичну схему і склад, які забезпечать максимальну сумарну эфективність.
Вхідні дані
У першому рядку вхідного файлу записано два цілих числа N і K (11 ≤ N ≤ 30000, 1 ≤ K ≤ 10). У кожному з наступних N рядків задано по 4 цілих числа – ефективності гравця на позиції воротаря, захисника, напівзахисника і нападника відповідно. Ефективність є цілим числом від 0 до 100. У кожному з наступних K рядків задано по 3 цілих числа, які визначають тактичну схему – кількість захисників, напівзахисників та нападаючих, які повинні бути випущені на поле при виборі цієї схеми (сума цих чисел дорівнює 10).
Вихідні дані
У вихідний файл необхідно вивести одне число – максимальну загальну ефективність, якої можна досягти.