stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <cmath>

#include <stdio.h>

#include <queue>

#include <stack>

#include <climits>

#include <map>

#include <set>



using namespace std;



typedef long long ll;

typedef pair<int, int> P;



const ll mod = 1000000007;

const int inf = 1e9;

const long long INF = 1LL << 60;



const int MAX_V = 100010;

struct edge {

    int to,cost;

};

int V;

vector<edge> G[MAX_V];  //重み付き有効グラフの隣接リスト表現

int d[MAX_V];



void dijkstra(int s){

    //greater<P>を指定することでfirstが小さい順に取り出せるようにする

    priority_queue<P, vector<P>,greater<P> > que;

    fill(d,d+V,inf);

    d[s] = 0;

    que.push(P(0,s));



     while(!que.empty()){

         P p = que.top(); que.pop();     // firstは最短距離、secondは頂点の番号

         int v = p.second;

         if(d[v] < p.first) continue;  

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

             edge e = G[v][i];

             if(d[e.to] > d[v] + e.cost){

                 d[e.to] = d[v] + e.cost;

                 que.push(P(d[e.to],e.to));

             }

         }

    }

}



int main()

{

    int h,w;

    cin >> h >> w;

    V = 10;

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

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

            int c;  cin >> c;

            if(i == j) continue;

            struct edge e;

            e.to = j; e.cost = c;

            G[i].push_back(e);

        }

    }

    int ans = 0;

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

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

            int a; cin >> a;

            if(a == 1 || a == -1) continue;

            dijkstra(a);

            ans += d[1];

        }

    }

    cout << ans << endl;

}


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

#include <string>

#include <vector>

#include <algorithm>

#include <cmath>

#include <stdio.h>

#include <queue>

#include <stack>

#include <climits>

#include <map>

#include <set>



using namespace std;



typedef long long ll;

typedef pair<int, int> P;



const ll mod = 1000000007;

const int inf = 1e9;

const long long INF = 1LL << 60;   // INFの値は1152921504606846976



int n;

const int V_MAX = 305;

ll d[V_MAX][V_MAX];



void warshall_floyd(){

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

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

            if(d[i][k] == INF) continue;

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

                if(d[k][j] == INF) continue;

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

            }

        }

    }

}



int main()

{

    int h,w;

    n = 10;

    cin >> h >> w;

    int a[h][w];

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

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

            cin >> d[i][j];

        }

    }

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

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

            cin >> a[i][j];

        }

    }

    warshall_floyd();

    ll ans = 0;

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

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

            if(a[i][j] == -1) continue;

            else ans += d[a[i][j]][1];

        }

    }

    cout << ans << endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long i64;

const int MAXN = 100000 + 10;



int N;

i64 sum;

int answer;

vector <pair<int, int>>Adj[MAXN];



inline void addEdge(int u, int v, int w)

{

	Adj[u].emplace_back(v, w);

	Adj[v].emplace_back(u, w);

}



int centroid, val[MAXN], siz[MAXN], mx[MAXN];



void DFS(int cur, int fa)

{

	siz[cur] = 1, mx[cur] = 0;

	for(auto x : Adj[cur])

		if(x.first != fa)

		{

			val[x.first] = x.second;

			DFS(x.first, cur);

			siz[cur] += siz[x.first];

			mx[cur] = max(mx[cur], siz[x.first]);

		}



	mx[cur] = max(mx[cur], N - siz[cur]);

	if(mx[cur] * 2 < N)

		centroid = cur;

	if(siz[cur] * 2 == N)

		answer = val[cur];

	sum += 2LL * min(siz[cur], N - siz[cur]) * val[cur];

}



int main()

{

	int u, v, w;

	answer = 0x7F7F7F7F;

	cin >> N ;

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

		cin >> u >> v >> w, addEdge(u, v, w);



	DFS(1, 0);



	if(answer >= 0x7F7F7F7F)

		for(auto x : Adj[centroid])

			answer = min(answer, x.second);



	cout << sum - answer << endl ;

}


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

#include <algorithm>



using std::min;

using std::max;



const int MAXN=100111;

const int INF=1034567890;



int N;



struct Vert{

	int FE;

	int Size, Val;

} V[MAXN];



struct Edge{

	int y, c, next;

} E[MAXN<<1];



int Ecnt;



void addE(int a, int b, int c){

	++Ecnt;

	E[Ecnt].y=b;E[Ecnt].c=c;E[Ecnt].next=V[a].FE;V[a].FE=Ecnt;

}



void getSize(int at, int f=0){

	V[at].Size=1;

	for(int k=V[at].FE, to;k;k=E[k].next){

		to=E[k].y;

		if(to==f)	continue;

		getSize(to, at);

		V[at].Size+=V[to].Size;

	}

}



void getVal(int at, int f=0){

	V[at].Val=N-V[at].Size;

	for(int k=V[at].FE, to;k;k=E[k].next){

		to=E[k].y;

		if(to==f)	continue;

		getVal(to, at);

		V[at].Val=max(V[at].Val, V[to].Size);

	}

}



int getG(int at, int f=0){

	int ret=at;

	for(int k=V[at].FE, to;k;k=E[k].next){

		to=E[k].y;

		if(to==f)	continue;

		to=getG(to, at);

		if(V[to].Val<V[ret].Val)	ret=to;

	}

	return ret;

}



long long Calc(bool &v){

	long long ret=0LL;

	for(int i=1, s;i<=Ecnt;i+=2){

		s=min(V[E[i].y].Size, V[E[i+1].y].Size);

		ret+=2LL*min(s, N-s)*E[i].c;

		if(s==N-s)	{ret-=(long long)(E[i].c);v=true;}

	}

	return ret;

}



int main(){

	

	scanf("%d", &N);

	

	for(int i=1, a, b, c;i<N;++i){

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

		addE(a, b, c);addE(b, a, c);

	}

	

	int at=1;

	getSize(at);getVal(at);at=getG(at);

	

	bool v=false;

	long long Ans=Calc(v);

	if(!v){

		int m=INF;

		for(int k=V[at].FE;k;k=E[k].next)	m=min(m, E[k].c);

		Ans-=(long long)m;

	}

	

	printf("%lld\n", Ans);

	

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>



using namespace std;

using namespace __gnu_pbds;

 

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define fbo find_by_order

#define ook order_of_key

 

typedef long long ll;

typedef pair<int,ll> ii;

typedef vector<int> vi;

typedef long double ld; 

typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

typedef set<ll>::iterator sit;

typedef map<ll,ll>::iterator mit;



int siz[111111];

vector<ii> adj[111111];



void prep(int u, int p)

{

	siz[u]=1;

	for(int i=0;i<adj[u].size();i++)

	{

		int v=adj[u][i].fi;

		if(v==p) continue;

		prep(v,u);

		siz[u]+=siz[v];

	}

}

int n;

int centroid(int u, int p)

{

	for(int i=0;i<adj[u].size();i++)

	{

		int v=adj[u][i].fi;

		if(v==p) continue;

		if(siz[v]*2>n)

		{

			return centroid(v,u);

		}

	}

	return u;

}



ll ans=0;



void solve(int u, int p)

{

	for(int i=0;i<adj[u].size();i++)

	{

		int v=adj[u][i].fi; ll w=adj[u][i].se;

		if(v==p) continue;

		ans+=ll(2)*siz[v]*w;

		//cerr<<u<<' '<<v<<' '<<w<<' '<<2*siz[v]<<'\n';

		solve(v,u);

	}

}



int main()

{

	ios_base::sync_with_stdio(0); cin.tie(0);

	cin>>n;

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

	{

		int u,v,w;

		cin>>u>>v>>w;

		u--; v--;

		adj[u].pb(mp(v,w));

		adj[v].pb(mp(u,w));

	}

	prep(0,-1);

	int cent = centroid(0,-1);

	prep(cent,-1);

	ll mini=ll(1e18);

	for(int i=0;i<adj[cent].size();i++)

	{

		int v=adj[cent][i].fi; ll w=adj[cent][i].se;

		if(siz[v]>=(n+1)/2)

		{

			mini=w;

			break;

		}

		mini=min(mini,w);

	}

	ans-=mini;

	solve(cent,-1);

	cout<<ans<<'\n';

}


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

using namespace std;

#define MN 100005

#define inf 0x3f3f3f3f

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*f;

}

struct edge{int t,nex,w;}e[MN*2];int hr[MN],cnt;

void ins(int f,int t,int w){e[++cnt]=(edge){t,hr[f],w};hr[f]=cnt;}

int n,a,b,c,dind,l[MN],r[MN],sons[MN],mson[MN],mins=inf,mid;

long long ans;

void dfs(int x,int fa,int w){

	l[x]=++dind;int maxi=0;

	for(int i=hr[x];i;i=e[i].nex)

		if(e[i].t!=fa){

			dfs(e[i].t,x,e[i].w);

			sons[x]+=sons[e[i].t]+1;

			maxi=max(maxi,sons[e[i].t]+1);

	}

	r[x]=dind;

	int mini=min(r[x]-l[x]+1,n-r[x]+l[x]-1);

	ans+=(long long) mini*w*2;

	maxi=max(maxi,n-1-sons[x]);

	mson[x]=maxi;

	if(maxi<mins) mins=maxi,mid=x;

}

int main(){

	n=read();register int i;

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

		a=read(),b=read(),c=read();

		ins(a,b,c);ins(b,a,c);

	}

	dfs(1,0,0);int lowe=inf;

	for(i=hr[mid];i;i=e[i].nex){

		lowe=min(lowe,e[i].w);

		if(mson[e[i].t]==mson[mid]){

			printf("%lld\n",ans-e[i].w);

			return 0;

		}

	}

	printf("%lld\n",ans-lowe);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

#define maxn 500100

#define lson root << 1

#define rson root << 1 | 1

#define lent (t[root].r - t[root].l + 1)

#define lenl (t[lson].r - t[lson].l + 1)

#define lenr (t[rson].r - t[rson].l + 1)

#define N 1111

#define eps 1e-6

#define pi acos(-1.0)

#define e exp(1.0)

using namespace std;

const int mod = 1e9 + 7;

typedef long long ll;

typedef unsigned long long ull;

char s[maxn];

int a[maxn];

int len;

bool check(int x)

{

    int sum = x * 9, cnt = 0;

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

    {

        sum += a[i];

        cnt += sum % 10;

        sum /= 10;

    }

    while (sum > 0)

    {

        cnt += sum % 10;

        sum /= 10;

    }

    return cnt <= x * 9;

}

int main()

{

    while (~scanf("%s", s))

    {

        memset(a, 0, sizeof(a));

        len = strlen(s);

        reverse(s, s + len);

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

            a[i] = (s[i] - '0') * 9;

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

        {

            a[i + 1] += a[i] / 10;

            a[i] %= 10;

        }

        if (a[len])

            len++;

        int l = 0, r = len * 2, ans = -1;

        while (l < r)

        {

            int mid = l + r >> 1;

            if (check(mid))

            {

                ans = mid;

                r = mid;

            }

            else

                l = mid + 1;

        }

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

    }

    return 0;

}


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

using namespace std;



#define ll long long

#define pb push_back



const int maxn = 1e5 + 20;



string s;



int mkay()

{

	int n = s.size();



	s[n - 1]++;

	for(int j = n - 1; j >= 0; j--)

	{

		if(s[j] <= '9')

			return j;



		s[j - 1]++;

		s[j] = '0';

	}

}



int main()

{

	ios_base::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);



	cin >> s;



	int n = s.size() , res = 0;

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

	{

		res++;

		int n = s.size();

		int last = i , j = i + 1;



		while(j < n && s[j] >= s[j - 1])

		{

			if(s[j] > s[j - 1])

				last = j;

			j++;

		}



		if(j == n)

			break;



		while(i < last + 1)

			s[i] = '0' , i++;

		i--;



		if(mkay() <= j)

			continue;



		i++;

		while(i < j)

		{

			s[i] = '0';

			res++;

			i++;



			if(mkay() <= j)

				break;

		}

		i--;



	}



	cout << res << endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

char s[1000001];

char t;

int	ans;

int a[1000001];

bool check(int x)

{

	int n=strlen(s+1),kum=0;

	for(int i=1;i<=n;i++) a[i]=(s[i]-'0')*9;

	a[1]+=9*x;

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

	{

		if(a[i]>9)

		{

			if(i==n) a[++n]=0;

			a[i+1]+=a[i]/10;

			a[i]%=10;

		}

	}

	for(int i=1;i<=n;i++) kum+=a[i];

	return kum<=x*9;

}

int main()

{

	scanf("%s",s+1); 

	int l=1,r=strlen(s+1);

	reverse(s+1,s+r+1);

	while(l<=r)

	{

		int mid=(l+r)/2;

		if(check(mid)==1)

			ans=mid,r=mid-1;

		else

			l=mid+1;

	}

	cout << ans << endl;

	return 0;

} 

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

#include<cstring>

#include<algorithm>

using namespace std;

char num[555555];

int j,sum=0,a[555555];

int main()

{

	scanf("%s",num);

	int n=strlen(num);

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

	{

		a[i]=(num[n-i]-'0')*9;

	}

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

	{

		a[i+1]+=a[i]/10;a[i]%=10;

	}

	if(a[n+1])

	{

		n++;

	}

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

	{

		sum+=a[i];

	}

	for(int k=1;k<=n*10;k++)

	{

		a[1]+=9;

		sum+=9;

		j=1;

		while(j<=n)

		{

			if(a[j]<10)

			{

				break;

			}

			sum-=10;

			a[j]-=10;

			sum++;

			a[j+1]++;

			j++;

			if(j==n&&a[j+1])

			{

				n++;

			}

		}

		if(sum<=9*k)

		{

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

			return 0;

		}

	}

	return 0;

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

#include<cstdio>

#include<cstring>

using namespace std;

#define MAX 500500

char ch[MAX];

int a[MAX<<1],n,s;

int main()

{

	scanf("%s",ch+1);n=strlen(ch+1);

	for(int i=n;i;--i)a[i]=(ch[n-i+1]-48)*9;

	for(int i=1;i<=n;++i)a[i+1]+=a[i]/10,a[i]%=10;

	if(a[n+1])++n;

	for(int i=1;i<=n;++i)s+=a[i];

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

	{

		a[1]+=9;int p=1;s+=9;

		while(a[p]>=10)

		{

			s-=a[p+1];a[p+1]+=a[p]/10;s+=a[p+1];

			s-=a[p];a[p]%=10;s+=a[p];

			++p;if(p>n)n=p;

		}

		if(s<=i*9){printf("%d\n",i);return 0;}

	}

	return 0;

}


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

#include<cstring>

#include<algorithm>

using namespace std;

char num[555555];

int j,sum=0,a[555555];

int main()

{

	scanf("%s",num);

	int n=strlen(num);

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

	{

		a[i]=(num[n-i]-'0')*9;

	}

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

	{

		a[i+1]+=a[i]/10;a[i]%=10;

	}

	if(a[n+1])

	{

		n++;

	}

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

	{

		sum+=a[i];

	}

	for(int k=1;k<=n*10;k++)

	{

		a[1]+=9;

		sum+=9;

		j=1;

		while(j<=n)

		{

			if(a[j]<10)

			{

				break;

			}

			sum-=10;

			a[j]-=10;

			sum++;

			a[j+1]++;

			j++;

			if(j==n&&a[j+1])

			{

				n++;

			}

		}

		if(sum<=9*k)

		{

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

			return 0;

		}

	}

	return 0;

}
// Slower C++ solution:
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <sstream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cctype>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <iterator>

#include <bitset>

#include <ctime>

#include<complex>

using namespace std;



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

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

#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

#define FILL(a,value) memset(a, value, sizeof(a))



#define SZ(a) (int)a.size()

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

#define PB push_back

#define MP make_pair



typedef long long LL;

typedef vector<int> VI;

typedef pair<int, int> PII;



const double PI = acos(-1.0);

const int INF = 1000 * 1000 * 1000 + 7;

const LL LINF = INF * (LL)INF;



const int MAX = 5 * 100000 + 47;

const int MOD = 1000 * 1000 * 1000 + 7;



int A[MAX];

string s;

int n;

int summ = 0;



void addOne()

{

	FOR(i, 0, n)

	{

		if (A[i] != 9)

		{

			summ++;

			A[i]++;

			break;

		}



		summ -= 9;

		A[i] = 0;

	}

}



int main()

{

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

	//freopen("out.txt", "w", stdout);

	ios::sync_with_stdio(false); cin.tie(0);

	cin >> s;

	n = SZ(s);

	FOR(i, 0, n)

	{

		A[i] = s[n - i - 1] - '0';

	}



	int nex = 0;

	FOR(i, 0, n + 1)

	{

		int val = A[i] * 9 + nex;

		A[i] = val % 10;

		nex = val / 10;

	}



	if (A[n]) n++;

	FOR(i, 0, n)

	{

		summ += A[i];

	}



	FOR(k, 1, MAX)

	{

		FOR(i, 0, 9)

		{

			addOne();

		}



		if (summ <= 9 * k)

		{

			cout << k << endl;

			return 0;

		}

	}

}

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

#include<cstring>

#include<algorithm>

#define maxn 500005

using namespace std;

int n,x[maxn],sum;

char s[maxn];

int main()

{

	scanf("%s",s+1);

	n=strlen(s+1);

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

	for(int i=1;i<=n;i++) x[i]=(s[i]-'0')*9;

	for(int i=1;i<=n;i++) x[i+1]+=x[i]/10,x[i]%=10;

	if(x[n+1]) n++;

	for(int i=1;i<=n;i++) sum+=x[i];

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

	{

		int v=9,j=1;

		while(v)

		{

			sum-=x[j],x[j]+=v;

			v=x[j]/10,x[j]%=10;

			sum+=x[j];

			if(j>n) n++;

			j++;

		}

		if(sum<=9*k) { printf("%d\n",k); return 0; }

	}

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



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

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

#define RET(x) { cout << x; exit(0); }

#define smin(a,b) a=min(a,b)

#define smax(a,b) a=max(a,b)

#define SZ(x) ((ll)((x).size()))

#define PB push_back

#define ER(x) cout << #x << ' ' << x << '\n';

#define X first

#define Y second



typedef long long int LL;

typedef LL ll;

typedef vector<ll> vll;

typedef pair<ll,ll> pll;

typedef string str;



const ll M=5e5+5,LG=30,mod=924844033;

ll pw(ll x,ll y){ if (y==0) return 1; return pw(x*x%mod,y/2)*(y&1?x:1)%mod; }



#define MOK(x) if (x>=mod) x-=mod;



struct bignum{

  ll ar[M];

  ll siz=0;

  void read(str s){

    while (SZ(s)){

      ar[siz]=s.back()-'0';

      s.pop_back();

      siz++;

    }

  }

  void mult9(){

    ll e=0;

    For(i,0,siz){

      ll p=ar[i]*9+e;

      e=p/10;

      ar[i]=p%10;

    }

    if (e){

      ar[siz++]=e;

    }

  }

  void plusplus(){

    for (ll i=0;1;i++){

      if (ar[i]!=9){

	ar[i]++;

	if (ar[siz]) siz++;

	return;

      }

      ar[i]=0;

    }

  }

  void decer(){

    ar[siz-1]--;

    while (siz && ar[siz-1]==0) siz--;

  }

  bool is0(){

    return (siz==0);

  }

  void chap(){

    For(i,0,siz) cout << ar[i];

    cout << '\n';

  }

};



bignum n;

  

int main(){

  ios::sync_with_stdio(0);

  str s;

  cin >> s;

  n.read(s);

  n.mult9();

  //n.chap();

  //return 0;

  ll tused=0;

  while (!n.is0()){

    n.plusplus();

    n.decer();

    tused++;

    //ER(tused);

    //n.chap();

    //if (tused>20) return 0;

  }

  RET((tused+8)/9);

}


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

#include<cstring>

#include<algorithm>

#define maxn 500005

using namespace std;

int n,x[maxn],sum;

char s[maxn];

int main()

{

	scanf("%s",s+1);

	n=strlen(s+1);

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

	for(int i=1;i<=n;i++) x[i]=(s[i]-'0')*9;

	for(int i=1;i<=n;i++) x[i+1]+=x[i]/10,x[i]%=10;

	if(x[n+1]) n++;

	for(int i=1;i<=n;i++) sum+=x[i];

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

	{

		int v=9,j=1;

		while(v)

		{

			sum-=x[j],x[j]+=v;

			v=x[j]/10,x[j]%=10;

			sum+=x[j];

			if(j>n) n++;

			j++;

		}

		if(sum<=9*k) { printf("%d\n",k); return 0; }

	}

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

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#define SF scanf

#define PF printf

#define MAXN 110

#define MOD 1000000007

#define eisiorti sort

using namespace std;

int a[MAXN];

int n;

int dp[MAXN/2][MAXN][MAXN];

int main(){

	SF("%d",&n);

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

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

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

	dp[n][1][0]=1;

	for(int i=n;i>=2;i--){

		int al=(a[i-1]!=a[i]);

		int ar=(a[2*n-i+1]!=a[2*n-i]);

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

			for(int r=0;r+l<=2*n-1;r++)

				if(dp[i][l][r]){

					for(int dl=1;dl<=l+al;dl++)

						(dp[i-1][l+al-dl+1][r+ar+(dl>1)]+=dp[i][l][r])%=MOD;	

					for(int dr=1;dr<=r+ar;dr++)

						(dp[i-1][l+al+1][r+ar-dr]+=dp[i][l][r])%=MOD;	

				}

	}

	int ans=0;

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

		for(int r=0;r+l<=2*n-1;r++)

			(ans+=dp[1][l][r])%=MOD;

	PF("%d",ans);

}

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

#include<algorithm>

using namespace std;

#define MAXN 55

#define MO 1000000007

void Add(int &x,int y)

{

	x=(x+y>=MO)?(x+y-MO):(x+y);

}

int dp[MAXN][MAXN*2][MAXN*2],n,a[MAXN*2],ans;

int main()

{

	scanf("%d",&n);

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

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

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

	dp[n][1][0]=1;

	for(int i=n-1;i>=1;i--)

	{

		int al=(a[i]!=a[i+1]),ar=(a[n*2-i]!=a[n*2-i-1]);

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

			for(int r=0;r+l<=2*n-1;r++)

				if(dp[i+1][l][r])

				{

					int t=dp[i+1][l][r];

					for(int dl=0;dl<l+al;dl++)

						Add(dp[i][l+al-dl][r+ar+(dl>0)],t);

					for(int dr=1;dr<=r+ar;dr++)

						Add(dp[i][l+al+1][r+ar-dr],t);

				}

	}

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

		for(int r=0;r+l<=2*n-1;r++)

			Add(ans,dp[1][l][r]);

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

}
// Slower C++ solution:


// dpの練習

// dpでなく、愚直に組んだプログラミング

// ナップサック問題とほぼ同じ



#include <iostream>

#include <algorithm>

#include <cstring>



using namespace std;



int wei; // 持てる最大の重さ

int n; // お宝の数

int v[1001]; // お宝の価値

int w[1001]; // お宝の重さ

 // グローバル配列は0で初期化されている

int dp[1001][1001]; //メモテーブル



int max_value(int i, int j) {

  int value;



  if( dp[i][j] >= 0 ){

    return dp[i][j];

    //すでに１回は調べている

  }

 

  if (i == n) {

    // 品物がもう残っていないときは、価値の和の最大値は0で確定

    //もうお宝がないつまり、価値は0

    value = 0;

  } else if (j < w[i]) {

    //風呂敷が持てる重さを超えてしまう

    // 残りの容量が足りず品物iを入れられないので、入れないパターンだけ処理

    // i+1 以降の品物のみを使ったときの最大値をそのままこの場合の最大値にする

    value = max_value(i + 1, j);

  } else {

    //左がお宝を入れない、右がお宝を入れた場合

    // 品物iを入れるか入れないか選べるので、両方試して価値の和が大きい方を選ぶ

    value = max( max_value(i + 1, j), max_value(i + 1, j - w[i]) + v[i] );

  } 

  return dp[i][j] = value;

  //メモに記憶させる

}



void max_weight( int ans ){



  int w_min;

   

  for (int i = wei -1 ; i >= 0 ; i--){

    if( ans != max_value( 0 , i ) ){

         w_min = i + 1;

         break;

    }

  }

  cout << w_min << endl;  

}





int main(void){



  int cnt = 1;

  while( cin >> wei ){

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

    //まだ調べてないところを-1で初期化

    if( wei == 0 )break;

    cin >> n;

    char ten;

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

      cin >> v[i] >> ten >> w[i];

    }

    cout << "Case " << cnt << ":" << endl;

    int ans = max_value( 0 , wei );

    cout << ans << endl;

    max_weight(ans);

    cnt++;

  }

  return 0;

}

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

#include <cstring>

#include <algorithm>

#define MAX 1000

using namespace std;



int main(void){



  int n,W;

  int w[MAX+1];

  int v[MAX+1];

  int dp[MAX+1][MAX+1];

  char ten;

  int cnt = 1;



  while( cin >> W , W ){

    cin >> n;

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

      cin >> v[i] >> ten >> w[i];

    }



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

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

	dp[i][j] = 0;

      }

    }



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

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

	if(j < w[i] ) dp[i+1][j] = dp[i][j];

	else dp[i+1][j] = max( dp[i][j] , dp[i][j-w[i]] + v[i] );

      }

    }

    

    cout << "Case " << cnt++ << ":" << endl;

    for( int i = W ; i >= 0 ; i-- ){

      if( dp[n][i] != dp[n][W] ){

	cout << dp[n][W] << endl << i+1 << endl;

	break;

      }

    }

  }  

  return 0;

}