Football club
Modern football clubs have a lot of players in their staff, but only 11 players can participate in a starting lineup in a particular match. One of them (goalkeeper) take the place near own team goal and is permitted to touch the ball with hands or arms within own penalty area. Other players have also some jobs and positions in the field. Defenders are mainly located on own side of the field, their job is to stop opposing attacking players from scoring. Midfielders are acted in the middle of field, helping to defenders or forwards, depending on game situation. And finally, forwards are located primarily on opposite side of the field and are responsible for scoring goals.
Indeed each player can play at any position, but his efficiency at one position will be greater than at other position. This particularly depends on the experience of playing at corresponding position, individual skills and other factors. The number of players at each position, except goalkeeper, can vary, but must be conformed to one of allowed formations.
You are a manager of the football club called ACM ILAN. There are N players in the club. For each player, his efficiency at each position is known. There are also K formations. You can choose and distribute players with respect to one of these formations.
Write the program determining most suitable formation and starting lineup providing maximal total efficiency.
Input
The first line of the input file contains two integers N and K (11 ≤ N ≤ 30000, 1 ≤ K ≤ 10). Each of following N lines consists of 4 integers – player efficiencies at position of goalkeeper, defender, midfielder and forward respectively. Efficiency is an integer between 0 and 100 inclusively. Each of last K lines contains 3 integers, determining allowed formation – the number of defenders, midfielders and forwards in starting lineup when choosing this formation (the sum of these numbers is equal 10).
Output
Output one number, the maximal total efficiency of starting lineup.