stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<stdio.h>

#include<map>

#include<algorithm>

using namespace std;

typedef pair<int,int> P;

P mt[200];

int dp[1000][201];//hでn個のときのrの最小値

int min(int a,int b){return a<b?a:b;}

int max(int a,int b){return a>b?a:b;}

int main(){

	int n,m;

	int i,j,k;

	while(1){

	scanf("%d",&n);

	if(n==0)return 0;

	for(i=0;i<n;i++){

		int a,b;

		scanf("%d %d",&a,&b);

		mt[i]=P(a,b);

	}

	scanf("%d",&m);

	for(i=0;i<m;i++){

		int a,b;

		scanf("%d %d",&a,&b);

		mt[n+i]=P(a,b);

	}

	sort(mt,mt+m+n);

	for(i=0;i<1000;i++)for(j=0;j<=m+n;j++)dp[i][j]=1000;

	for(i=0;i<m+n;i++){

		int h=mt[i].first;

		int r=mt[i].second;

		dp[h][1]=min(dp[h][1],r);

		for(j=0;j<h;j++){

			for(k=0;k<m+n;k++){

				if(r>dp[j][k])dp[h][k+1]=min(dp[h][k+1],r);

			}

		}

	}

	int ans=0;

	for(i=0;i<1000;i++)for(j=0;j<=m+n;j++){

		if(dp[i][j]!=1000)ans=max(ans,j);

	}

	printf("%d\n",ans);

	}

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

int dp[200];//iが一番外の最大値

int h[200];

int r[200];

int m,n;

int max(int a,int b){return a>b?a:b;}

int dfs(int x){

	if(dp[x]!=-1)return dp[x];

	int i;

	int ans=1;

	for(i=0;i<m+n;i++){

		if(h[i]<h[x]&&r[i]<r[x])ans=max(ans,dfs(i)+1);

	}

	return dp[x]=ans;

}

int main(){

	while(1){

	scanf("%d",&m);

	if(m==0)return 0;

	int i;

	for(i=0;i<m;i++)scanf("%d %d",&h[i],&r[i]);

	scanf("%d",&n);

	for(i=0;i<n;i++)scanf("%d %d",&h[i+m],&r[i+m]);

	int ans=1;

	for(i=0;i<m+n;i++)dp[i]=-1;

	for(i=0;i<m+n;i++)ans=max(ans,dfs(i));

	printf("%d\n",ans);

	}

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>



using namespace std;



int main() {

	int n;

	while ( cin >> n, n ) {

		vector<int> h(n), r(n);

		for (int i = 0; i < n; ++i) {

			cin >> h[i] >> r[i];

		}

		int M; cin >> M;

		h.resize(n+M);

		r.resize(n+M);

		for (int i = 0; i < M; ++i) {

			cin >> h[n+i] >> r[n+i];

		}

		n += M;



		int m[200][200] = {0};

		for (int i = 0; i < n; ++i) {

			for (int j = 0; j < n; ++j) {

				if (h[i] < h[j] && r[i] < r[j]) {

					m[i][j] = -1;

				}

			}

		}

		int ans = 0;

		for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {

			if (m[i][k] && m[k][j]) {

				m[i][j] = min(m[i][j], m[i][k] + m[k][j]);

			}

			ans = min(ans, m[i][j]);

		}

		cout << (-ans + 1) << endl;

	}

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>



using namespace std;



typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

typedef pair<ll, ll> P;



#define EACH(i,a) for (auto& i : a)

#define FOR(i,a,b) for (ll i=(a);i<(b);i++)

#define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);i--)

#define REP(i,n) for (ll i=0;i<(n);i++)

#define RREP(i,n) for (ll i=(n)-1;i>=0;i--)

#define debug(x) cout<<#x<<": "<<x<<endl

#define pb push_back

#define ALL(a) (a).begin(),(a).end()



const ll linf = 1e18;

const int inf = 1e9;

const double eps = 1e-12;

const double pi = acos(-1);



template<typename T>

istream& operator>>(istream& is, vector<T>& vec) {

	EACH(x,vec) is >> x;

	return is;

}

/*

template<class... T>

ostream& operator<<(ostream& os, tuple<T...>& t) {

	for (size_t i = 0; i < tuple_size< tuple<T...> >::value; ++i) {

		if (i) os << " ";

		os << get<0>(t);

	}

	return os;

}

*/

template<typename T>

ostream& operator<<(ostream& os, vector<T>& vec) {

	REP(i,vec.size()) {

		if (i) os << " ";

		os << vec[i];

	}

	return os;

}

template<typename T>

ostream& operator<<(ostream& os, vector< vector<T> >& vec) {

	REP(i,vec.size()) {

		if (i) os << endl;

		os << vec[i];

	}

	return os;

}



int main() {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	int N;

	while ( cin >> N, N ) {

		vector<P> v;

		REP(i, N) {

			int h, r; cin >> h >> r;

			v.pb( P(h, r) );

		}

		int M; cin >> M;

		REP(i, M) {

			int h, r; cin >> h >> r;

			v.pb( P(h, r) );

		}

		sort( ALL(v) );

		N += M;

		vector< vector<int> > dp(N+1, vector<int>(N+1, -1)); dp[0][0] = 0;

		REP(i, N) {

			REP(j, N+1) {

				if (dp[i][j] < 0) continue;

				dp[i+1][j] = max(dp[i+1][j], dp[i][j]);

				if (j == 0 || (v[j-1].first < v[i].first && v[j-1].second < v[i].second)) {

					dp[i+1][i+1] = max(dp[i+1][i+1], dp[i][j]+1);

				}

			}

		}

		int ans = -1;

		REP(i, N+1) ans = max(ans, dp[N][i]);

		cout << ans << endl;

	}

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include "bits/stdc++.h"

using namespace std;

int main()

{

ios_base::sync_with_stdio(false);

int n;

cin >> n;

long long a[2*n+1];

for(int i = 0; i < 2*n; i++)cin >> a[i];

sort(a,a+2*n);

long long sum = 0;

for(int i = 0; i < 2*n; i+=2)

{

sum+=a[i];

}

cout << sum;

return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

int n,a[2001],sum=0;



inline void init() {

	scanf("%d",&n);

	n*=2;

	for (int i=1;i<=n;i++) scanf("%d",&a[i]);

	sort(a+1,a+n+1);

}



inline void work() {

	for (int i=1;i<=n;i++) 

		if (i%2==1) 

			sum+=a[i]; 

}



int main() {

	init();

	work();

	printf("%d\n",sum);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



const int N = 211;



int a[N];



int main() {

	ios :: sync_with_stdio(0);

	int n; cin >> n;

	for(int i = 0; i < 2 * n; i ++)

		cin >> a[i];

	sort(a, a + 2 * n);

	int ans = 0;

	for(int i = 0; i < 2 * n; i += 2)

		ans += a[i];

	cout << ans << '\n';

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

int n,a[2001],sum=0;



inline void init() {

	scanf("%d",&n);

	n*=2;

	for (int i=1;i<=n;i++) scanf("%d",&a[i]);

	sort(a+1,a+n+1);

}



inline void work() {

	for (int i=1;i<=n;i++) 

		if (i%2==1) 

			sum+=a[i]; 

}



int main() {

	init();

	work();

	printf("%d\n",sum);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

int n,a[210],s=0;

int main()

{

	cin>>n;

	for (int i=1;i<=2*n;i++)

	  cin>>a[i];

	sort(a+1,a+2*n+1);

	for (int i=1;i<=2*n;i+=2)

	  s+=a[i];

	cout<<s;

    return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int n,s[1010];

int main(){

	scanf("%d",&n); n<<=1;

	for(int i=1;i<=n;++i) scanf("%d",s+i);

	sort(s+1,s+1+n);

	for(int i=1;i<=n;i+=2) *s+=min(s[i],s[i+1]);

	printf("%d\n",*s);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>



using namespace std;



const int N = 1234;

long long a[N] , ans , n;



int main()

{

	cin >> n;

	for(int i = 0 ; i < 2 * n ; i++)

		cin >> a[i];

	sort(a , a + (2 * n));

	for(int i = 0 ; i < n * 2 ; i++)

	{

		if((i + 1) % 2)

		{

			ans += a[i];

		}

	}

	cout << ans;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int n,s[1010];

int main(){

	scanf("%d",&n); n<<=1;

	for(int i=1;i<=n;++i) scanf("%d",s+i);

	sort(s+1,s+1+n);

	for(int i=1;i<=n;i+=2) *s+=min(s[i],s[i+1]);

	printf("%d\n",*s);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<algorithm>

#include<iostream>



using namespace std;

int L[205];

int main()

{

	int N;

	int sum=0;

	int min;

	while(~scanf("%d",&N))

	{

		for(int i=0;i<2*N;i++)

		{

			cin>>L[i];

		}

		sort(L,L+2*N);

		

		for(int j=0;j<2*N;j=j+2)

		{

			min=L[j]<L[j+1] ? L[j] : L[j+1];

			sum=sum+min;

		}

		cout<<sum<<endl;

	}

} 

// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<algorithm>

using namespace std;

int aa[230];

main()

{

	int n;

	while(~scanf("%d",&n))

	{

		int i;

		for(i=0;i<n*2;i++)

		{

			scanf("%d",&aa[i]);

		}

		sort(aa,aa+2*n);

		int min,num=0;

		for(i=0;i<2*n;i=i+2)

		{

			min=aa[i]<aa[i+1]?aa[i]:aa[i+1];

			num+=min;

		}

		printf("%d\n",num);

	}

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<algorithm>

using namespace std;

int a[105];

int main(){

	int n,ans;

	cin>>n;

	for (int i=1;i<=n*2;i++)cin>>a[i];

	sort(a+1,a+n*2+1);

	ans=0;

	for (int i=1;i<=n*2-1;i+=2) ans+=a[i];

	cout<<ans<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<algorithm>

using namespace std;

int aa[230];

main()

{

	int n;

	while(~scanf("%d",&n))

	{

		int i;

		for(i=0;i<n*2;i++)

		{

			scanf("%d",&aa[i]);

		}

		sort(aa,aa+2*n);

		int min,num=0;

		for(i=0;i<2*n;i=i+2)

		{

			min=aa[i]<aa[i+1]?aa[i]:aa[i+1];

			num+=min;

		}

		printf("%d\n",num);

	}

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 200

int n;

int L[MAXN+5],ans=0;

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n*2;i++)

		scanf("%d",&L[i]);

	sort(L+1,L+n*2+1);

	for(int i=1;i<=2*n;i+=2)ans+=L[i];

	printf("%d",ans);//

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<algorithm>

using namespace std;

int main()

{   int n,s=0,i;

 	scanf("%d",&n);

	int a[2*n];

	for(i=0;i<n*2;i++)

	scanf("%d",&a[i]);

	  sort(a,a+n+n);

		for(i=0;i<n*2;i++)

		if(i%2==0)

		s+=a[i];

    printf("%d\n",s);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//in the name of Allah ;

#include<bits/stdc++.h>

using namespace std ;

int arr[1000] ;

int main ()

{

	int n , ans = 0;

	cin >> n ;

	n *= 2 ; 

	for ( int i = 0 ;i < n ; i++ ) 

		cin >> arr[i];

	sort ( arr, arr+n ) ;

	for ( int i = 0 ; i < n ; i+= 2 ) 

		ans += min ( arr[i] , arr[i+1] ) ;

	cout << ans << endl;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<algorithm>

using namespace std;

int main()

{   int n,s=0,i;

 	scanf("%d",&n);

	int a[2*n];

	for(i=0;i<n*2;i++)

	scanf("%d",&a[i]);

	  sort(a,a+n+n);

		for(i=0;i<n*2;i++)

		if(i%2==0)

		s+=a[i];

    printf("%d\n",s);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

const int Maxn=400;

int a[Maxn],maj,n;

int main(){

	cin>>n;

	for(int i=0;i<(2*n);i++){

		cin>>a[i];

	}

	sort(a,a+(2*n));

	for(int i=0;i<(2*n);i+=2){

		maj+=a[i];

	}

	cout<<maj;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<algorithm>

using namespace std;

int main()

{   int n,s=0,i;

 	scanf("%d",&n);

	int a[2*n];

	for(i=0;i<n*2;i++)

	scanf("%d",&a[i]);

	  sort(a,a+n+n);

		for(i=0;i<n*2;i++)

		if(i%2==0)

		s+=a[i];

    printf("%d\n",s);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#define _USE_MATH_DEFINES

#include <algorithm>

#include <cmath>

#include <iostream>

#include <vector>

using namespace std;



int main() {

	int N; cin >> N;

	vector<int> r(N);

	for (int i = 0; i < N; i++)

		cin >> r[i];

	sort(r.begin(), r.end());

	double ma = 0;

	for (int n = 3; n <= N; n++) {

		vector<int> a(r.end() - n, r.end());

		do {

			vector<double> x(n), y(n);

			for (int i = 0; i < n; i++) {

				x[i] = a[i] * cos(M_PI*2 / n * i);

				y[i] = a[i] * sin(M_PI*2 / n * i);

			}

			for (int t = 0; t < 1000; t++) {

				int i = rand() % n;

				int j = (i + n - 1) % n, k = (i + 1) % n;

				double dx = x[k] - x[j], dy = y[k] - y[j];

				double _dx = dy, _dy = -dx;

				double r = sqrt(_dx * _dx + _dy * _dy);

				x[i] = _dx / r * a[i];

				y[i] = _dy / r * a[i];

			}

			double sum = 0;

			for (int i = 0; i < n; i++) {

				int j = (i + 1) % n;

				sum += x[i] * y[j] - y[i] * x[j];

			}

			ma = max(ma, sum);

		} while (next_permutation(a.begin() + 1, a.end()));

	}

	printf("%.15f\n", ma / 2);

}

// Optimized solution to the same problem (faster):
#define _USE_MATH_DEFINES

#include <algorithm>

#include <cmath>

#include <iostream>

#include <vector>

using namespace std;



int main() {

	int N; cin >> N;

	vector<int> r(N);

	for (int i = 0; i < N; i++)

		cin >> r[i];

	sort(r.begin(), r.end());

	double ma = 0;

	for (int n = 3; n <= N; n++) {

		vector<int> a(r.end() - n, r.end());

		do {

			vector<double> x(n), y(n);

			for (int i = 0; i < n; i++) {

				x[i] = a[i] * cos(M_PI*2 / n * i);

				y[i] = a[i] * sin(M_PI*2 / n * i);

			}

			for (int t = 0; t < 3; t++) {

				int i = rand() % n;

				int j = (i + n - 1) % n, k = (i + 1) % n;

				double dx = x[k] - x[j], dy = y[k] - y[j];

				double _dx = dy, _dy = -dx;

				double r = sqrt(_dx * _dx + _dy * _dy);

				x[i] = _dx / r * a[i];

				y[i] = _dy / r * a[i];

			}

			double sum = 0;

			for (int i = 0; i < n; i++) {

				int j = (i + 1) % n;

				sum += x[i] * y[j] - y[i] * x[j];

			}

			ma = max(ma, sum);

		} while (next_permutation(a.begin() + 1, a.end()));

	}

	printf("%.15f\n", ma / 2);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//メモリ数確認したか?

#include<iostream>

#include<cstdio>

#include<string>

#include<vector>

#include<algorithm>

#include<cstdlib>

#include<math.h>

#include<set>

#include<map>

#include<queue>

using namespace std;

typedef long long int ll;



int main()

{

    int N,K;

	int C[2000],G[2000];

	vector<int>X[10];

	scanf("%d%d",&N,&K);

	for(int i=0;i<N;i++){

		scanf("%d%d",&C[i],&G[i]);

		X[G[i]-1].push_back(C[i]);

	}

	for(int i=0;i<10;i++){

		sort(X[i].begin(),X[i].end());

		reverse(X[i].begin(),X[i].end());

	}

	int sum[10][2001];

	for(int i=0;i<10;i++){

		sum[i][0]=0;

		for(int j=1;j<=X[i].size();j++){

			sum[i][j]=sum[i][j-1]+X[i][j-1]+2*(j-1);

		}

	}

	int dp[2001];

	fill(dp,dp+N+1,0);

	for(int i=0;i<10;i++){

		for(int j=2000-X[i].size();j>=0;j--){

			for(int k=0;k<=X[i].size();k++){

				dp[j+k]=max(dp[j+k],dp[j]+sum[i][k]);

			}

		}

	}

	printf("%d\n",dp[K]);

    return 0;

}

//メモリ数確認したか?

// Optimized solution to the same problem (faster):
#include<iostream>

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

int N, K;

vector<int>G[10];

vector<int>Gsum[10];

int dp[10][2000];

int main()

{

	scanf("%d%d", &N, &K);

	for (int i = 0; i < N; i++){

		int A, B;

		scanf("%d%d", &A, &B);

		G[B - 1].push_back(A);

	}

	for (int i = 0; i < 10; i++){

		sort(G[i].begin(), G[i].end());

		reverse(G[i].begin(), G[i].end());

	}

	for (int i = 0; i < 10; i++){

		Gsum[i].push_back(0);

		

		for (int j = 0; j < G[i].size(); j++){

			int sum = 0;

			for (int k = 0; k <= j; k++){

				sum += G[i][k];

			}

			sum += (j + 1)*j;

			if (G[i].size()>0)Gsum[i].push_back(sum);

		}

	}

	for (int j = 0; j <= min(K, (int)Gsum[0].size() - 1); j++)dp[0][j] = Gsum[0][j];

	for (int i = 1; i < 10; i++){

		for (int j = 0; j <= K; j++){

			int dpij = 0;

			for (int k = 0; k <= min(j, (int)Gsum[i].size()-1);k++){

				dpij = max(dpij,dp[i - 1][j - k] + Gsum[i][k]);

			}

			dp[i][j] = dpij;

		}

	}

	

	int ans = 0;

	for (int i = 0; i <= K; i++)ans = max(ans, dp[9][i]);

	printf("%d\n", ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
/*

 *  ん？今何でもするって

 *  言ってないね

 */



#include <stdio.h>

#include <stdlib.h>



int dp[2 << 10][2001];

int books[10][2001];

int book_nums[10];

int sell_prices[10][2001];



int greater_int(const void *a, const void *b) {

    return *(int*)b - *(int*)a;

}



int main() {

    int a, b, c, d;

    int n, k;

    int book_bits;

    int max;



    scanf("%d %d", &n, &k);

    for (a=0; a<n; a++) {

        int c, g;

        int ind;



        scanf("%d %d", &c, &g);

        --g;

        ind = book_nums[g];

        books[g][ind] = c;

        ++book_nums[g];

    }

        

    for (a=0; a<10; a++) {

        qsort(books[a], book_nums[a], sizeof(int), greater_int);



        sell_prices[a][1] = books[a][0];

        for (b=2; b<=book_nums[a]; b++) {

            sell_prices[a][b] = sell_prices[a][b-1] + books[a][b-1] + (b-1)*2;

        }

    }



    book_bits = 1 << 10;

    for (a=0; a<k; a++) {

        for (b=0; b < book_bits; b++) {

            for (c=0; c<10; c++) {

                int num;



                if ((b >> c) & 1) continue;



                num = book_nums[c];

                if (num > k-a) {

                    num = k-a;

                }



                for (d=1; d<=num; d++) {

                    int val = dp[b][a] + sell_prices[c][d];

                    int *p = &dp[b | 1 << c][a+d];



                    if (*p < val) *p = val;

                }

            }

        }

    }



    max = 0;

    for (a=0; a < book_bits; a++) {

        if (max < dp[a][k]) {

            max = dp[a][k];

        }

    }



    printf("%d\n", max);

}

// Optimized solution to the same problem (faster):
/*

 *  低知能マン

 */



#include <stdio.h>

#include <stdlib.h>



int dp[11][2001];

int books[10][2001];

int book_nums[10];

int sell_prices[10][2001];



int greater_int(const void *a, const void *b) {

    return *(int*)b - *(int*)a;

}



int main() {

    int a, b, c, d;

    int n, k;

    int max;



    scanf("%d %d", &n, &k);

    for (a=0; a<n; a++) {

        int c, g;

        int ind;



        scanf("%d %d", &c, &g);

        --g;

        ind = book_nums[g];

        books[g][ind] = c;

        ++book_nums[g];

    }

        

    for (a=0; a<10; a++) {

        qsort(books[a], book_nums[a], sizeof(int), greater_int);



        sell_prices[a][1] = books[a][0];

        for (b=2; b<=book_nums[a]; b++) {

            sell_prices[a][b] = sell_prices[a][b-1] + books[a][b-1] + (b-1)*2;

        }

    }



    for (a=0; a<10; a++) {

        for (b=0; b<k; b++) {

            int num;



            num = book_nums[a];

            if (num > k-b) {

                num = k-b;

            }



            for (c=0; c<=num; c++) {

                int val = dp[a][b] + sell_prices[a][c];

                int *p = &dp[a+1][b+c];



                if (*p < val) *p = val;

            }

        }

    }



    max = 0;

    for (a=0; a<=10; a++) {

        if (max < dp[a][k]) {

            max = dp[a][k];

        }

    }



    printf("%d\n", max);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cmath>

#include <queue>

#include <tuple>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

int n, m, c, a, b;

int main() {

	ios::sync_with_stdio(false);

	while (cin >> n >> m, n | m) {

		vector<vector<pair<int, int> > > v(n);

		for (int i = 0; i < n; i++) {

			cin >> c;

			for (int j = 0; j < c; j++) {

				cin >> a >> b;

				v[i].push_back(make_pair(a, b));

			}

		}

		vector<vector<vector<int> > > d(n);

		for (int i = 0; i < n; i++) d[i] = vector<vector<int> >(v[i].size(), vector<int>(m + 1, 999999999));

		priority_queue<tuple<int, int, int, int> > que; // (dist, y, x, z)

		for (int i = 0; i <= 1 && i <= m; i++) {

			for (int j = 0; j < v[i].size(); j++) {

				d[i][j][i] = 0;

				que.push(make_tuple(0, i, j, i));

			}

		}

		while (!que.empty()) {

			tuple<int, int, int, int> t1 = que.top(); que.pop();

			int a1 = -get<0>(t1), b1 = get<1>(t1), c1 = get<2>(t1), d1 = get<3>(t1);

			for (int i = 1; i <= 2 && b1 + i < n; i++) {

				if (i == 2 && d1 == m) continue;

				for (int j = 0; j < v[b1 + i].size(); j++) {

					int s = abs(v[b1][c1].first - v[b1 + i][j].first) * (v[b1][c1].second + v[b1 + i][j].second);

					if (d[b1 + i][j][d1 + i - 1] > a1 + s) {

						d[b1 + i][j][d1 + i - 1] = a1 + s;

						que.push(make_tuple(-d[b1 + i][j][d1 + i - 1], b1 + i, j, d1 + i - 1));

					}

				}

			}

		}

		int ret = 999999999;

		for (int i = 0; i <= 1 && i <= m; i++) {

			for (int j = 0; j < v[n - i - 1].size(); j++) {

				for (int k = 0; k <= m - i; k++) {

					ret = min(ret, d[n - i - 1][j][k]);

				}

			}

		}

		cout << ret << endl;

	}

}

// Optimized solution to the same problem (faster):
#include <cmath>

#include <cstdio>

#include <algorithm>

#pragma warning(disable : 4996)

using namespace std;

int n, m, c[155], p[155][15], v[155][15], dp[155][15][79];

int main() {

	while (scanf("%d%d", &n, &m), n) {

		for (int i = 0; i < n; i++) {

			scanf("%d", &c[i]);

			for (int j = 0; j < c[i]; j++) scanf("%d%d", &p[i][j], &v[i][j]);

		}

		for (int i = 1; i < n; i++) {

			for (int j = 0; j < c[i]; j++) {

				for (int k = 0; k <= m; k++) {

					dp[i][j][k] = 999999999;

					for (int l = 0; l < c[i - 1]; l++) {

						dp[i][j][k] = min(dp[i][j][k], dp[i - 1][l][k] + abs(p[i][j] - p[i - 1][l]) * (v[i][j] + v[i - 1][l]));

					}

					if (k == 0) continue;

					if (i == 1) {

						dp[i][j][k] = 0;

						continue;

					}

					for (int l = 0; l < c[i - 2]; l++) {

						dp[i][j][k] = min(dp[i][j][k], dp[i - 2][l][k - 1] + abs(p[i][j] - p[i - 2][l]) * (v[i][j] + v[i - 2][l]));

					}

				}

			}

		}

		int ret = 999999999;

		for (int i = 0; i < c[n - 1]; i++) ret = min(ret, dp[n - 1][i][m]);

		if (m >= 1) for (int i = 0; i < c[n - 2]; i++) ret = min(ret, dp[n - 2][i][m - 1]);

		printf("%d\n", ret);

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <stdio.h>

#include <string.h>

#include <math.h>

#include <iostream>

#include <algorithm>

#include <string>

#include <vector>

#include <set>

#include <queue>

#include <map>

#include <unordered_map>

using namespace std;



typedef long long ll;

typedef pair<int, int> pii;



const int maxn = 1e5 + 10;

const int INF = 0x3f3f3f3f;

const ll LL_INF = 0x3f3f3f3f3f3f3f3f;



#define dbg(x1) cout<<#x1<<" = "<<(x1)<<endl

#define dbg2(x1,x2) cout<<#x1<<" = "<<(x1)<<" "<<#x2<<" = "<<(x2)<<endl

#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<(x1)<<" "<<#x2<<" = "<<(x2)<<" "<<#x3<<" = "<<(x3)<<endl

int dp[200][20000];

int a[maxn];

int main() {

    //freopen(".in", "r", stdin);

    int n;scanf("%d",&n);

    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    dp[0][0]=1;

    for(int i=1;i<=n;i++)

    {

        for(int j=0;j<=10000;j++) dp[i][j]=dp[i-1][j];

        for(int j=a[i];j<=10000;j++)

        {

            dp[i][j]=(dp[i][j]|dp[i-1][j-a[i]]);

        }

    }

    int ans=0;

    for(int i=1;i<=10000;i++)

    {

        if(dp[n][i]&&(i%10!=0)) ans=i;

    }

    printf("%d\n",ans);

    return 0;

}




// Optimized solution to the same problem (faster):
#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cstring>

#include<cmath>

#include<ctime>

#include<algorithm>

#include<utility>

#include<stack>

#include<queue>

#include<vector>

#define INF 0x3f3f3f3f

#define LL long long

const int MOD = 1E9+7;

const int N = 1000000+5;

const int dx[] = {-1,1,0,0,-1,-1,1,1};

const int dy[] = {0,0,-1,1,-1,1,-1,1};

using namespace std;

 

int main() {

    int n;

    scanf("%d",&n);

    int sum=0;

    int minn=INF;

    bool flag=false;

    for(int i=1; i<=n; i++){

        int x;

        scanf("%d",&x);

        sum+=x;

        if(x%10!=0){

            flag=true;

            minn=min(minn,x);

        }

    }

 

    if(!flag)

        printf("0\n");

    else{

        if(sum%10!=0)

            printf("%d\n",sum);

        else

            printf("%d\n",sum-minn);

    }

 

    return 0;

}

// Fastest known solution for this problem: