package xj; import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner;
public class Game { static int T,N,mincost; static int []dataA; static int []dataM; public static void main(String[] args) throws FileNotFoundException { /*Scanner sc=new Scanner(System.in);*/ Scanner sc=new Scanner(new File("src/game")); T=sc.nextInt(); for (int t = 0; t < T; t++) { N=sc.nextInt(); dataA=new int [N]; dataM=new int[N]; for (int i = 0; i < N; i++) { dataA[i]=sc.nextInt(); dataM[i]=sc.nextInt(); } mincost=0xfffffff; dfs(0,0,0,0,0); System.out.println("#"+(t+1)+" "+mincost); } } private static void dfs(int step, int money, int s1, int s2, int s3) { if(step==N){ if(money<mincost){mincost=money;} return; } if(money>=mincost){return;} //买关过关 dfs(step+1,money+dataM[step],s1,s2,s3); //买兵过关 dfs(step+1,money+2*dataM[step],s1,s2,s3+dataA[step]); //攻打过关 if(s1+s2+s3>=dataA[step]){ if(s1>=dataA[step]){ s1=s2; s2=s3; s3=0; } else if(s1+s2>=dataA[step]){ s1=s1+s2-dataA[step]; s2=s3; s3=0; } else{ s1=0; s2=s1+s2+s3-dataA[step]; s3=0; } dfs(step+1,money,s1,s2,s3); } }
}
//input
5 7 10 100 70 5 80 15 20 60 50 90 30 80 10 10 9 600 800 300 400 300 400 1000 400 300 600 100 300 600 300 600 500 1000 300 11 1000 10 700 900 400 500 300 10 900 900 300 10 50 900 50 900 700 900 500 900 50 10 20 896 546 543 216 454 310 408 367 40 602 252 582 954 627 850 234 763 479 232 278 301 538 528 508 936 154 629 443 758 336 432 700 882 256 278 738 517 882 317 136 20 410 610 831 909 675 629 421 774 386 869 544 219 492 414 996 557 499 482 231 285 804 978 304 881 489 911 75 315 927 648 252 914 330 396 937 133 495 882 813 717
//output
#1 150 #2 3000 #3 2370 #4 4721 #5 8231
