Məsələlər
Футбольный клуб
Футбольный клуб
Современные футбольные клубы имеют в своей структуре большое количество футболистов, однако на конкретный матч в составе команды могут выйти лишь \textbf{11} человек. При этом один из них (вратарь) становится на защиту ворот и имеет право играть руками в своей штрафной площади. Остальные же игроки также имеют свои задачи и позиции на поле. Так защитники располагаются в основном на своей половине поля, их задача -- противодействовать нападающим игрокам команды-соперника. Полузащитники действуют в середине поля, помогая защитникам или нападающим в зависимости от игровой ситуации. И наконец нападающие располагаются преимущественно на половине поля соперника и стараются забить гол в чужие ворота.
На самом деле, каждый игрок может действовать на любой позиции, однако при этом на одной позиции его полезность будет выше, чем на другой. Это зависит, в частности, от опыта игры на соответствующей позиции, набранной им на данный момент игровой формы и других факторов. Количество игроков на каждой позиции, кроме вратарской, может быть каким угодно, однако должно укладываться в одну из принятых тактических схем.
Вы -- главный тренер футбольного клуба ACM Ilan. В вашем распоряжении \textbf{N} игроков, для каждого из которых известна его эффективность на каждой позиции. Есть также \textbf{K} тактических схем, по которым могут распределяться полевые игроки вашей команды.
Напишите программу, определяющую наиболее подходящую тактическую схему и состав, которые обеспечат максимальную суммарную эффективность.
\InputFile
В первой строке входного файла записано два целых числа \textbf{N} и \textbf{K} (\textbf{11} ≤ \textbf{N} ≤ \textbf{30000}, \textbf{1} ≤ \textbf{K} ≤ \textbf{10}). В каждой из последующих \textbf{N} строк задается по \textbf{4} целых числа -- эффективности игрока на позиции вратаря, защитника, полузащитника и нападающего соответственно. Эффективность является целым числом от \textbf{0} до \textbf{100}. В каждой из последующих \textbf{K} строк задаются по \textbf{3} целых числах, определяющих тактическую схему -- количество защитников, полузащитников и нападающих, которые должны быть выпущены на поле при выборе этой схемы (сумма этих чисел равна \textbf{10}).
\OutputFile
В выходной файл необходимо вывести одно число -- максимальную общую эффективность, которой можно добиться.
Giriş verilənləri #1
12 3 90 10 10 10 20 50 40 30 20 90 20 70 30 60 20 60 30 70 20 20 20 80 50 70 80 20 20 20 10 20 40 80 20 30 80 30 10 20 90 60 10 40 40 90 10 50 20 80 4 4 2 4 3 3 3 4 3
Çıxış verilənləri #1
850