#include <bits/stdc++.h>
using namespace std;
#define int long long
//fixed << setprecision()
const int length = 3005;
int n, k;
int arr[length][4];
int ans = INT_MAX;

int f[length][3 * length];



signed main()
{
	ios::sync_with_stdio(false);
	cin >> n >> k;
	memset(arr, 0, sizeof arr);
	for(int i = 1;i <= n;i++)
	{
		cin >> arr[i][1] >> arr[i][2] >> arr[i][3];
	}
	memset(f, 0x3f, sizeof f);
	
	f[0][0] = f[0][1] = f[0][2] = f[0][3] = 0;
	
	for(int i = 1;i <= n;i++)
	{
		for(int j = 3;j <= k + 3;j++)
		{
			f[i][j] = min({
				f[i - 1][j], 
				f[i - 1][j - 1] + arr[i][1], 
				f[i - 1][j - 2] + arr[i][2], 
				f[i - 1][j - 3] + arr[i][3]
						});
		}
	}
	
	
	
	cout << f[n][k + 3] << endl;
	
	 
	return 0;
}