#include <iostream>#include <stdio.h>#include <memory.h>#include <stdlib.h>#include <limits.h>using namespace std;#define inf INT_MAXint f[10010][10][10],pre[10010][10][10],n,m,w[1010],out[10010];int main(){ int i,j,k,ans,p,q,tem,x,y,now; while(scanf("%d%d",&m,&n)!=EOF) { memset(w,0,sizeof(w)); for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); w[x]=y; } for(j=0;j<=9;j++) { for(k=0;k<=9;k++) { f[2][j][k]=0; } } for(now=3;now<=n;now++) // dp { for(i=0;i<=9;i++) { for(j=0;j<=9;j++) { f[now][i][j]=-inf; for(k=0;k<=9;k++) { if(f[now-1][j][k]+w[100*i+10*j+k]>f[now][i][j]) { f[now][i][j]=f[now-1][j][k]+w[100*i+10*j+k]; pre[now][i][j]=k; } } } } } ans=-inf; for(i=0;i<=9;i++) { for(j=0;j<=9;j++) { if(f[n][i][j]>ans) { ans=f[n][i][j]; p=i; q=j; } } } i=n; while(i>2) { printf("%d",p); tem=pre[i][p][q]; p=q; q=tem; i--; } printf("%d%dn",p,q); } return 0;}
