#include<bits/stdc++.h>
using namespace std;
char in[100], out[100];
long long int A[200100], B[200100], C[200100], D[200100];
int main(){
	for(int I=1;I<=20;I++){
    	long long int T, n=10, k, i, ans;
        sprintf(in,".%d.in",I);
		freopen(in,"w",stdout);
		if(I<10) n = I *10;
		else n = 100000;
		k = rand() % min(100ll, n);  
		
		printf("%lld %lld\n", n, k);
        C[n+1]=D[n+1]=0;
        for(i=1;i<=n;i++){
        	A[i] = ((rand() * rand() + rand())%1000+1000)%1000+1;
        	B[i] = ((rand() * rand() + rand())%1000+1000)%1000+1;
			printf("%lld %lld\n", A[i], B[i]); 
		} 
        for(i=n;i>0;i--){
            C[i] = min(D[i+1],C[i+1])+A[i];
            D[i] = min(D[i+1],C[i+1])+B[i];
        }
        sprintf(in,".%d.out",I);
		freopen(in,"w",stdout);
        ans = C[1];
        for(i=2;i<=k;i++) ans = min(ans, C[i]);
        printf("%lld\n", ans);
    }
}