题目描述

给定$\red{n}$个作业的集合$\red{J＝{J_1,J_2,…,J_n }}$。每一个作业$\red{J_i}$都有两项任务分别在两台机器上完成。每个作业必须先由机器$\red{1}$处理，然后由机器$\red{2}$处理。作业$\red{J_i}$需要机器j的处理时间为$\red{t_{ji}}$，其中$\red{i＝1,2,…,n，j＝1,2}$。对于一个确定的作业调度，设$\red{F_{ji}}$是作业$\red{i}$在机器$\red{j}$上完成处理的时间。所有作业在机器$\red{2}$上完成处理的时间和$\red{f=\displaystyle\sum_{i=1}^{n}F_{2i}}$

称为该作业调度的完成时间和$\red{(n<=15)}$。

批处理作业调度问题要求对于给定的$\red{n}$个作业，制定最佳调度方案，使其完成时间和达到最小。

批处理作业调度问题的一个常见例子是在计算机系统中完成一批$\red{n}$个作业，每个作业都先完成计算，然后将计算结果打印输出。计算任务由计算机的中央处理器完成，打印输出任务由打印完成。在这种情形下，计算机的中央处理器是机器$\red{1}$，打印是机器$\red{2}$。

对于批处理作业调度问题，可以证明，存在最佳作业调度使得在机器$\red{1}$和机器$\red{2}$上作业以相同次序完成。例如，考虑如下$\red{n＝3}$的实例。

这$\red{3}$个作业的$\red{6}$种可能的调度方案是$\red{1，2，3；1，3，2；2，1，3；2，3，1；3，1，2；3，2，1}$；它们所对应的完成时间和分别是$\red{19，18，20，21，19，19}$。显而易见，最佳调度方案是$\red{1，3，2}$，其完成时间和为$\red{18}$。

样例

输入样例

6        

3 8

12 10

5 9

2 6

9 3

11 1

输出样例

154