405369: GYM101917 B Three Couse Meal

You go to a fancy restaurant with exactly K out of your N friends, this restaurant offers a three-course meal, first comes the appetizer, then the main entrance, and lastly dessert. Since this is a fancy restaurant you can't start the next course until everyone in the table finishes eating their current dish. You want to choose which friends are going to dinner with you in such a way that everyone in the table finishes the three-course meal as soon as possible. You can assume you will always eat equally fast or faster than the fastest eaters among your friends and that the time to serve and prepare all the dishes is 0.

Two integers N and K ($$$1<=N<=2000, 1<K<=N$$$), the amount of friends you have and the exact amount of friends that are going to dine with you. N lines, each containing the integers, A, E, D ($$$1<=A,E,D<=10{^9}$$$), the amount of time in minutes that it takes for each of your friends to eat their appetizer, main entrance and dessert, respectively.

A single integer, the least amount of time it will take to eat the three course meal with K of your friends.

3 1
1 1 1
1 2 1
1 1 2

3

3 2
1 1 1
1 2 1
1 1 2

4

5 3
5 7 9
3 11 5
9 4 1
1 5 9
2 4 2

21