/* 予選課題解答プログラム (2001.7.2) */
#include <stdio.h>
#define INT_MAX 2147483647
#define N 500

int main(int argc, char *argv[]){
  FILE *fp;

  int a,b;  
  int i,j,k,l;
  int q;

  int p[N+1];
  int m[N+1][N+1];
  int n;
  int lastb;

  /** 入力 **/
  fp = fopen(argv[1], "r");
  n = 0;
  while(fscanf(fp, "%d %d",&a, &b) != EOF){
    p[n++] = a; lastb = b;
  }
  p[n] = lastb;

  /** costを計算 : 動的計画法を利用。ナイーブにプログラムを書いた
      場合, 再帰的な構造になる。再帰の内側に繰り返し計算される
      場所が存在する。再帰構造は以下の漸化式を前提としているが、
      左辺の値をもとめる時,「すでに」右辺の値は求められるいる
      (再帰を底まで実行しなくてよい)ので、以下のような単純な繰り返し
      計算で求めることができる。*/
  /** m[i,j] = min(m[i,k] + m[k+1,j] + (p[i-1]+p[k]+p[j]) ) **/

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

  for (l=2; l<=n; l++){
    for (i=1; i<=n-l+1; i++){
      j = i+l-1;
      m[i][j] = INT_MAX;
      for (k=i; k<=j-1; k++){
	q = m[i][k] + m[k+1][j]+(p[i-1]+p[k]+p[j]);
	if (q < m[i][j]){
	  m[i][j] = q;
	}
      }
    }
  }

  /** 出力 **/
  printf("Cost = %d\n", m[1][n]);
  return 0;
}