租车

牛牛有两辆车，但是他的家就在牛客公司的隔壁，每天上班只需步行就可以。所以他经常把两辆车租出去来赚取外快。在热闹的国庆节期间，很多人想要租借他的车来外出游玩。因此他想请你来合理分配时间，使得最大程度上减少汽车接送所有客户并返回原点所需要的时间。

客户需要前往的区域由n个地点表示，这些地点的标号是0--n-1，其中一些地点可以由道路连接，道路情况由一个矩阵描述，其中矩阵的第 i 行的第 j 个数字表示从地点 i 到地点 j 所需要的时间。如果地点 i 到地点 j 没有路径，则显示为 0。接下来会输入客户的信息，两个正整数分别表示客户的位置和目的地的位置。客户不在乎哪辆车来接送他们，也不在乎什么时候能到达目的地，但是一旦客户一旦被汽车接到，汽车就必须将这个顾客送到目的地才能接送其他顾客（汽车可以自动行驶）。客户不能在中间的地点下车，也不会互相分享汽车，因此如果汽车接送了一个顾客，则他不能再接送其他的顾客。汽车的出发位置是地点 0，在接送完所有顾客后，两辆汽车必须均返回 0 点才算运送结束。