import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); int[] w=new int[n]; for(int i=0;i=3 for(int i=0;i<2;i++){//1番目の頂点を拾うかどうか for(int j=1;j<=n;j++){//j番目まで確定 for(int k=0;k<=j&&k<=m;k++){//頂点数 for(int l=0;l<2;l++){//i番目の頂点を拾うかどうか if(l==1&&i==0){ // 1番目とi番目の頂点を拾う、拾わないの関係から、現在の頂点数に制約 if(!(k<=j-1)){ dp[i][l][k][j]=-10000000; continue; }else if(k==0){ dp[i][l][k][j]=-10000000; continue; }else if(m-k>n-j){ dp[i][l][k][j]=-10000000; continue;//確定していない残り箇所がこれから塗らないといけない箇所の数より小さい } }else if(l==1&&i==1){ if(j==1&&k==1){//1番目しか確定しておらず、1着色 dp[i][l][k][j]=0; continue; }else if(k<2){ dp[i][l][k][j]=-1000000000;//着色される箇所が確定している箇所より多い continue; }else if(m-k>n-j){ dp[i][l][k][j]=-10000000; continue;//確定していない残り箇所がこれから塗らないといけない箇所の数より小さい } }else if(l==0&&i==0){ if(j==1){ if(k>j-1) dp[i][l][k][j]=-10000000; continue; }else if(k>j-2){ dp[i][l][k][j]=-10000000; continue; }else if(m-k>n-j){ dp[i][l][k][j]=-10000000; continue;//確定していない残り箇所がこれから塗らないといけない箇所の数より小さい } }else if(l==0&&i==1){ if(!(k<=j-1)){ dp[i][l][k][j]=-10000000; continue; }else if(k==0){ dp[i][l][k][j]=-10000000; continue; }else if(m-k>n-j){ dp[i][l][k][j]=-10000000; continue;//確定していない残り箇所がこれから塗らないといけない箇所の数より小さい } } // 1番目の頂点での操作 if(j==1){ dp[i][l][k][j]=0; }else if(k==0){ dp[i][l][k][j]=0; // dp[1番目の頂点を拾うかどうか(i)][j番目の頂点を拾うかどうか(l)][頂点数k][jまで確定]; }else if(l==0){ dp[i][l][k][j]=Math.max(dp[i][0][k][j-1],dp[i][1][k][j-1]); }else if(l==1){ dp[i][l][k][j]=Math.max(dp[i][1][k-1][j-1]+w[j-2],dp[i][0][k-1][j-1]); } } } } } dp[1][1][m][n]=dp[1][1][m][n]+w[n-1]; int max=Math.max(dp[1][1][m][n],dp[1][0][m][n]); max=Math.max(max,dp[0][1][m][n]); max=Math.max(max, dp[0][0][m][n]); max=Math.max(max, dp[1][0][m][n]); System.out.println(max); // for(int i=0;i<2;i++){//1番目の頂点を拾うかどうか // for(int j=1;j<=n;j++){//j番目まで確定 // for(int k=0;k<=j&&k<=m;k++){//頂点数 // for(int l=0;l<2;l++){//i番目の頂点を拾うかどうか // System.err.println("dp["+i+"]["+l+"]["+k+"]["+j+"]="+dp[i][l][k][j]); // } // } // // } // // } } }