#include<stdio.h>
#include<stdlib.h>

#ifndef min
 #define min(a,b) (((a)<(b))?(a):(b))
#endif

#define MAX 501       /* max num of terms, not of lines */
#define NUM ((MAX+1)*(MAX+2)>>1)
#define Table(start,length) cost_table[num[start]+length]

int count,term[MAX];
int cost_table[NUM];
int num[MAX],dec_num[MAX];

void init(char *filename)
{
 FILE *fp;
 int buf,h;

 fp=fopen(filename,"r");

 while(EOF!=fscanf(fp,"%d %d",&term[count],&buf)){
  count++;
 }
 term[count]=buf;
 count++;

 fclose(fp);

 for(h=1;h<count;h++){
  num[h]=num[h-1]+count+2-h;
  dec_num[h]=num[h]-h;
 }

 return;
}

int calc_cost(int head,int length1)
{
 int cost;
 int *p_cost_table1;
 int *p_cost_table2;
 int *p_num,*p_num_e;
 int length2;

 length2=length1-1;

 cost=min(Table(head+1,length1)+term[head],
   Table(head,length1)+term[head+length2]);

 p_cost_table1=&Table(head,3);
 p_cost_table2=&cost_table[length2]+head+2;
 p_num_e=&dec_num[head+length2];
 for(p_num=&dec_num[head+2];p_num<p_num_e;p_num++){
  cost=min(cost,*p_cost_table1+*(p_cost_table2+*p_num));
  p_cost_table1++;
 }

 return cost+term[head]+term[head+length1];
}

int main(int argc,char *argv[])
{
 int head,length;
 int t1,t2;

 init(argv[1]);

 /* length==3 */
 for(head=0;head<=count-3;head++){
  Table(head,3)=term[head]*2+term[head+1]+term[head+2];
 }

 /* length==4 */
 t1=term[0]+term[2];
 for(head=0;head<count-3;head++){
  t2=term[head+1]+term[head+3];
  Table(head,4)=term[head]+t1+t2+min(t1,t2);
  t1=t2;
 }

 for(length=5;length<=count;length++){
  for(head=0;head<=count-length;head++){
   Table(head,length)=calc_cost(head,length-1);
  }
 }

 printf("cost=%d\n",cost_table[count]-term[0]);

 return 0;
}