OI题库

【问题描述】
已知某生产车间有两条装配线，每条有N个装配站。装配线i的第j个装配站表示为Si,j。在该站的装配时间为ai,j。一个汽车底盘进入工厂，然后进入装配线i(i=1 或 i=2)，花费时间为ei。在通过一条线的第j个装配站后，这个底盘来到任一条线的第(j+1)个装配站。如果它留在相同的装配线，则没有移动的开销。但是，如果在装配站的Si,j后，移动到了另外一条线上，则花费时间ti,j。在离开一条线的第n个装配站后，完成的汽车花费时间xi后离开工厂。待求解的问题是应该在装配线1选择那些站，在装配线2选择那些站，才能使汽车通过工厂的时间最小
【输入格式】 
第一行输入一个数字n，每条装配线上有n个装配站。 
第二、三行各有2个数字，表示两条装配线进入、离开的时间。 
第四、五行各有n个数字，表示两条装配线每个站点的装配时间。 
第六、七行各有n-1个数字，表示两条装配线之间切换的时间。
【输出格式】 
第一行1个数字，表示总的最短装配时间 
第二行共n（1<=N<=10000）个数字，即经过的站点所在装配线的序号。 若有多种方案，输出字典序最小的方案。
【输入输出样例】
als.in
6 
2 3 
4 2 
7 9 3 4 8 4 
8 5 6 4 5 7 
2 3 1 3 4 
2 1 2 2 1
als.out
38 
1 2 1 2 2 1