2841: 大扫除
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：28
解决：7
题目描述
题目背景
DaisySunchaser：工作室剩下的房间你来扫吧
yemaster：不行，我实在是太累了
DaisySunchaser：可是我看你一直都在床上躺着啊
yemaster：这个嘛……在床上躺着也很累的嘛
DaisySunchaser：。。。。。。
yemaster：好好好，我扫还不行嘛。
（yemaster仍然在床上躺着）
yemaster：啊——什么东西飞过来了！
题目描述
yemaster只能被迫将工作室剩下的$N$个房间扫完。扫完第$i$个房间需要花费他$cost_i$点体力。同时，yemaster扫完一个房间后，还不得不花费体力到达另一个房间。具体地，yemaster从第$i$个房间走到第$j$个房间还需要额外花费$dist_{i,j}$的体力；由于NemoArce在工作室里随手扔了些奇怪的物品，导致不一定$dist_{i,j}=dist_{j,i}$。现在，yemaster决定从房间$0$出发，每次前往打扫所需花费体力最多的房间，并将其打扫完成。所有房间打扫完成后，yemaster还需回到房间$0$以归还工具。现在，yemaster想知道，自己这一趟需要花费多少体力，来提前吃自己最爱的小巧克力棒补充体力（注：房间$0$无需打扫）
输入
共$N+3$行
第$1$行，输入$N$
第$2$行，输入$cost_{1\sim N}$
第$3\sim N+3$行，第$i + 3$行输入$dist_{i, 0\sim N}$
输出
共一行，输出花费体力取模$1e9+7$的结果
样例输入 复制
3
2 3 1
0 2 1 1
1 0 6 2
4 3 0 1
1 1 1 0样例输出 复制
13提示
样例解释
$1.$ yemaster从房间$0$走到房间$2$（消耗体力为$3$，最大），消耗$1$体力
$2.$ yemaster打扫房间$2$，消耗$3$体力
$3.$ yemaster从房间$2$走到房间$1$（消耗体力为$2$，最大），消耗$3$体力
$4.$ yemaster打扫房间$1$，消耗$2$体力
$5.$ yemaster从房间$1$走到房间$3$（消耗体力为$1$，最大），消耗$2$体力
$6.$ yemaster打扫房间$3$，消耗$1$体力
$7.$ yemaster从房间$3$走到房间$0$，消耗$1$体力
共需$1+3+3+2+2+1+1=13$体力
数据范围
对于$100\%$的数据，$N\le 2\times 10^3,\; 0\le cost_i,\; dist_{i,j} \le 10^9,\; dist{i,i} = 0$
后记
yemaster：呼，终于扫完了，可累死我了
（敲门声）
？？？：您好，我是家政保洁，房子里有人吗？
yemaster：啊？
$1.$ yemaster从房间$0$走到房间$2$（消耗体力为$3$，最大），消耗$1$体力
$2.$ yemaster打扫房间$2$，消耗$3$体力
$3.$ yemaster从房间$2$走到房间$1$（消耗体力为$2$，最大），消耗$3$体力
$4.$ yemaster打扫房间$1$，消耗$2$体力
$5.$ yemaster从房间$1$走到房间$3$（消耗体力为$1$，最大），消耗$2$体力
$6.$ yemaster打扫房间$3$，消耗$1$体力
$7.$ yemaster从房间$3$走到房间$0$，消耗$1$体力
共需$1+3+3+2+2+1+1=13$体力
数据范围
对于$100\%$的数据，$N\le 2\times 10^3,\; 0\le cost_i,\; dist_{i,j} \le 10^9,\; dist{i,i} = 0$
后记
yemaster：呼，终于扫完了，可累死我了
（敲门声）
？？？：您好，我是家政保洁，房子里有人吗？
yemaster：啊？