Футбольний клуб#2161
Сучасні футбольні клуби мають у своєму складі багато гравців, але лише гравців можуть взяти участь у стартовому складі на конкретний матч. Один із них (воротар) займає місце біля воріт своєї команди та має право торкатися м’яча руками або передпліччями у межах свого штрафного майданчика. Інші гравці також мають визначені ролі та позиції на полі. Захисники здебільшого розташовані на своїй половині поля, і їхнє завдання — не допустити взяття воріт суперником. Півзахисники діють у центрі поля, допомагаючи або захисникам, або нападникам залежно від ігрової ситуації. Нарешті, нападники знаходяться переважно на половині суперника й відповідають за взяття воріт.
Кожен гравець може зіграти на будь-якій позиції, але його ефективність на певній позиції може бути вищою, ніж на інших. Це зокрема залежить від його досвіду на цій позиції, поточного ігрового стану та інших чинників. Кількість гравців на кожній позиції, окрім воротаря, може бути довільною, але повинна відповідати одній з дозволених схем розстановки.
Ви — менеджер футбольного клубу ACM Ilan. У клубі є гравців, і для кожного з них відома його ефективність на кожній позиції. Також є дозволених схем розстановки. Ви можете обрати та розподілити гравців згідно з однією з цих схем.
Напишіть програму, яка визначить найбільш підходящу схему розстановки та стартовий склад, що дасть максимальну сумарну ефективність.
У першому рядку вхідного файлу записано два цілих числа та (11 \leq N \leq 30000, 1 \leq K \leq 10). Кожен із наступних рядків містить цілих числа: ефективність гравця на позиціях воротаря, захисника, півзахисника та нападника відповідно. Ефективність — це ціле число від до включно. Кожен із наступних рядків містить цілих числа, що визначають дозволену схему розстановки: кількість захисників, півзахисників і нападників у стартовому складі при виборі цієї схеми (сума цих чисел дорівнює ).
Виведіть одне число — максимальну сумарну ефективність стартового складу.
Приклад 1