#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
long long dp[9000+5];
long long a[3000+5],b[3000+5],c[3000+5]; 
int main()
{
	int n,k;
	scanf("%d %d",&n,&k);
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;i++)
		scanf("%lld %lld %lld",&a[i],&b[i],&c[i]);		
	dp[0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=k;j>=3;j--)
		{
			dp[j]=min(min(min(dp[j],dp[j-1]+a[i]),dp[j-2]+b[i]),dp[j-3]+c[i]);
		}	
		dp[2]=min(min(dp[2],b[i]),dp[1]+a[i]);
		dp[1]=min(dp[1],a[i]);
	}
	cout<<dp[k];
	return 0;
}