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