题目内容

身为快递员，你每天都得离开仓站，把货送到若干客户处。各位客户各自给出可收货时段，货必须落在该时段内交到（早到可以停着等，晚到不行）。货都送完后，还得回到仓站。交通导致任意两处之间的行驶耗时已经给出（正反向未必相同）。请排出一条访问顺序，在所有可收货时段都满足的条件下，让离开仓站直到再次回到仓站所花的时长（把等候也算进去）尽量短。若怎样走都做不到，输出 $-1$。

一共给出 $m$ 处站点，编号写成 $0$ 到 $m-1$，其中 $0$ 处就是仓站。

站点 $p$ 各自对应可到达闭区间 $[lo_p,hi_p]$，意思是抵达该站的时刻必须落在 $lo_p$ 与 $hi_p$ 之间，两端都算合法。

仓站的可作业时段覆盖整天 $[0,1440]$（单位：分钟）。你在时刻 $0$ 离开仓站；途中允许在任意站点停着等（这段等候要算进总时长）。每位客户处必须经过且只经过一次，末了再回到仓站。行驶耗时表 $dur[p][q]$ 给出从站点 $p$ 走到站点 $q$ 要花多少分钟（$dur[p][p]=0$，正反向可以不同）。

请给出尽量短的总时长（也就是再次抵达仓站的那个时刻）；若无可行走法，输出 $-1$。

输入描述

首行给出一个整数 $m$（$2\le m\le15$），即站点一共有多少处（仓站也算在内）。

随后连续 $m$ 行，每行两个整数 $lo_p$ 与 $hi_p$（$0\le lo_p\le hi_p\le1440$），对应第 $p$ 处站点的可到达闭区间。

再随后 $m$ 行，每行 $m$ 个整数，构成行驶耗时表 $dur$；第 $p$ 行第 $q$ 列就是从 $p$ 走到 $q$ 的耗时（$0\le dur[p][q]\le1440$）。

输出描述

输出一个整数：尽量短的总时长（分钟）。若全部客户处无法按规则走完，输出 $-1$。

样例1

输入

4
0 1440
6 18
20 45
14 28
0 4 18 8
6 0 9 20
10 12 0 7
9 16 11 0

输出

36

说明

四处站点：仓站 $0$ 的可作业时段 $[0,1440]$，客户 $1$ 为 $[6,18]$，客户 $2$ 为 $[20,45]$，客户 $3$ 为 $[14,28]$。

最优走法 $0\to 1\to 2\to 3\to 0$：

• 去 $1$：耗时 $4$，抵达时刻 $4$，等到 $6$
• 去 $2$：耗时 $9$，抵达时刻 $15$，等到 $20$
• 去 $3$：耗时 $7$，抵达时刻 $27$，落在 $[14,28]$
• 回仓站：耗时 $9$，抵达时刻 $36$

另一条可行走法 $0\to 1\to 3\to 2\to 0$ 会在时刻 $47$ 才回到仓站，更长。故答案为 $36$。

样例2

输入

4
0 1440
5 12
5 12
5 12
0 4 4 4
4 0 10 10
4 10 0 10
4 10 10 0

输出

-1

说明

三位客户的可收货时段都是 $[5,12]$。从仓站到任一客户耗时 $4$，抵达后等到 $5$；客户之间互走耗时 $10$，再抵达已是时刻 $15$，超出闭区间上界。怎样排列都走不完，故输出 $-1$。