C++ :

#pragma GCC optimize ("O2")
#include <cstdio>
#include <algorithm>
#include <cstring>
#define F(x,y,z) for(register int x=y;x<=z;x++)
#define DF(x,y,z) for(register int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
const int MAXN=105;
template <typename T>
void read(T& x){
	T pd=1; char ch=getchar(); x=0;
	while(ch<'0'||ch>'9'){ if(ch=='-') pd=-1; ch=getchar(); }
	while('0'<=ch&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
	x*=pd;
}
int n,m;
int tim1[MAXN],tim2[MAXN];
int f[MAXN][MAXN][MAXN];
int main(){
//	freopen("599.in","r",stdin);
//	freopen("599.out","w",stdout);
	read(n); read(m);
	F(i,1,n){ read(tim1[i]); read(tim2[i]); }
	memset(f,0x3c3c3c3c,sizeof(f));
	F(i,0,m)
		F(j,0,m)
			f[1][i][j]=tim1[1]*i+tim2[1]*j;
	F(i,2,n){
		int temp=f[i-1][m][m];
		F(j,0,m)
			F(k,0,m)
				F(j1,0,j){
					if(tim1[i]*j1>temp) break;
					F(k1,0,k){
						if(tim1[i]*j1+tim2[i]*k1>temp) break;
						f[i][j][k]=min(f[i][j][k],max(f[i-1][j-j1][k-k1],tim1[i]*j1+tim2[i]*k1));
					}
				}
	}
	printf("%d",f[n][m][m]);
	
	return 0;
}