stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
//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;

}

// Faster C++ solution for the same problem (measured speedup: 5.202732061852194x):
#include<stdio.h>

#include<algorithm>

using namespace std;

int main()

{

	int n;

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

  {

	int a[2*n];

	int i;

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

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

	sort(a,a+2*n);

	int sum=0;

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

	sum+=a[i];

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

  }

	return 0;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.194657685171646x):
#include<stdio.h>

#include<algorithm>

using namespace std;

int main()

{

	int n;

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

  {

	int a[2*n];

	int i;

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

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

	sort(a,a+2*n);

	int sum=0;

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

	sum+=a[i];

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

  }

	return 0;

}
// Slower C++ solution:
#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);

}

// Faster C++ solution for the same problem (measured speedup: 1.2263348036940847x):
#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 < 100; 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);

}
// Slower C++ solution:
#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);

}

// Faster C++ solution for the same problem (measured speedup: 1.2418866037172684x):
#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 < 50; 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);

}
// Slower C++ solution:
#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);

}

// Faster C++ solution for the same problem (measured speedup: 1.2482594569928243x):
#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 < 30; 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);

}
// Slower C++ solution:
#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);

}

// Faster C++ solution for the same problem (measured speedup: 1.251361727785096x):
#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 < 20; 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);

}
// Slower C++ solution:
#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);

}

// Faster C++ solution for the same problem (measured speedup: 1.2561247428236046x):
#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 < 5; 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);

}
// Slower C++ solution:
#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);

}

// Faster C++ solution for the same problem (measured speedup: 1.2564336457465355x):
#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);

}
// Slower C++ solution:
//メモリ数確認したか?

#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;

}

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

// Faster C++ solution for the same problem (measured speedup: 1.1640953986513833x):
#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);

}
// Slower C++ solution:
/*

 *  ん？今何でもするって

 *  言ってないね

 */



#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);

}

// Faster C++ solution for the same problem (measured speedup: 2.826969900905094x):
/*

 *  低知能マン

 */



#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);

}
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <utility>



using namespace std;



typedef pair<int, int> pii;



#define fst first

#define scd second

#define rep(i,x) for(int i=0;i<(x);++i)



template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}



const int inf = 1e9;



int k[150];

vector<pii> stone[150];

int N, M;



int memo[150][150][10];



int rec(int n, int m, int i)

{

	if (n >= N - 1) return 0;



	if (~memo[n][m][i]) return memo[n][m][i];



	int res = inf;



	rep(j, k[n + 1]) {

		int dist = (stone[n][i].scd + stone[n + 1][j].scd) * abs(stone[n][i].fst - stone[n + 1][j].fst);

		chmin(res, dist + rec(n + 1, m, j));

	}



	if (m < M) {

		if (n + 2 >= N) return 0;

		rep(j, k[n + 2]) {

			int dist = (stone[n][i].scd + stone[n + 2][j].scd) * abs(stone[n][i].fst - stone[n + 2][j].fst);

			chmin(res, dist + rec(n + 2, m + 1, j));

		}

	}



	return memo[n][m][i] = res;

}



signed main()

{

	while (scanf("%d %d", &N, &M), N || M) {

		rep(i, N) {

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



			stone[i].resize(k[i]);



			rep(j, k[i]) {

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

				stone[i][j].fst = x, stone[i][j].scd = d;

			}

		}



		int ans = inf;



		rep(i, k[0]) {

			memset(memo, -1, sizeof(memo));

			chmin(ans, rec(0, 0, i));

		}



		if (M > 0) {

			rep(i, k[1]) {

				memset(memo, -1, sizeof(memo));

				chmin(ans, rec(1, 1, i));

			}

		}



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

	}

}

// Faster C++ solution for the same problem (measured speedup: 1.160185967447942x):
#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <utility>



using namespace std;



typedef pair<int, int> pii;



#define fst first

#define scd second

#define rep(i,x) for(int i=0;i<(x);++i)



template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}



const int inf = 1e9;



int k[150];

vector<pii> stone[150];

int N, M;



int memo[150][150][10];



int rec(int n, int m, int i)

{

	if (n >= N - 1) return 0;



	if (~memo[n][m][i]) return memo[n][m][i];



	int res = inf;



	rep(j, k[n + 1]) {

		int dist = (stone[n][i].scd + stone[n + 1][j].scd) * abs(stone[n][i].fst - stone[n + 1][j].fst);

		chmin(res, dist + rec(n + 1, m, j));

	}



	if (m < M) {

		if (n + 2 >= N) return 0;

		rep(j, k[n + 2]) {

			int dist = (stone[n][i].scd + stone[n + 2][j].scd) * abs(stone[n][i].fst - stone[n + 2][j].fst);

			chmin(res, dist + rec(n + 2, m + 1, j));

		}

	}



	return memo[n][m][i] = res;

}



int main()

{

	while (scanf("%d %d", &N, &M), N || M) {

		rep(i, N) {

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



			stone[i].resize(k[i]);



			rep(j, k[i]) {

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

				stone[i][j].fst = x, stone[i][j].scd = d;

			}

		}



		int ans = inf;



		memset(memo, -1, sizeof(memo));



		rep(i, k[0]) chmin(ans, rec(0, 0, i));



		if (M > 0) rep(i, k[1]) chmin(ans, rec(1, 1, i));



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

	}

}