Football club#2161
Modern football clubs have many players on their staff, but only players can participate in a starting lineup in a particular match. One of them (the goalkeeper) takes the place near their own team goal and is permitted to touch the ball with hands or arms within their own penalty area. Other players also have specific roles and positions on the field. Defenders are mainly located on their own side of the field, and their job is to stop opposing players from scoring. Midfielders act in the middle of the field, helping either the defenders or the forwards depending on the game situation. Finally, forwards are located primarily on the opponent's side of the field and are responsible for scoring goals.
Each player can play at any position, but their efficiency at one position may be higher than at another. This particularly depends on their experience at that position, current playing form, and other factors. The number of players at each position, except for the goalkeeper, can be arbitrary, but must conform to one of the allowed formations.
You are the manager of the football club ACM Ilan. There are players in the club, and for each player, their efficiency at each position is known. There are also allowed formations. You can choose and distribute players according to one of these formations.
Write a program to determine the most suitable formation and starting lineup providing the maximal total efficiency.
The first line of the input file contains two integers and (11 \leq N \leq 30000, 1 \leq K \leq 10).
Each of the next lines contains integers: the player's efficiency at the positions of goalkeeper, defender, midfielder, and forward, respectively. Efficiency is an integer between and inclusive.
Each of the next lines contains integers, which define an allowed formation: the number of defenders, midfielders, and forwards in the starting lineup when choosing this formation (the sum of these numbers is equal to ).
Output one number: the maximum total efficiency of the starting lineup.
Example 1