题目描述 小明去一个大型游乐园玩，游乐园里除了有很多游乐项目外，还有 n 个商店。第 i 个商店会在特定的时间 Pi 对当时在店里的顾客送出一份精美的礼物。小明很喜欢这些礼物，他希望拿到尽可能多的礼物，也就是说，他希望尽可能多地在某商店发放礼物的时候正好呆在店里。

经过一定的调查，小明弄清楚了从 i 号商店走到 j 号商店所需要的时间 Tij。虽然游乐园奇特的布局使得从 i 号商店到 j 号商店的最短路不一定是直接连接这两个商店的那条，但是小明并不会选择那些会经过其他商店的路线，只是直接走到目标商店等待礼物。此外，因为有些路是上下坡的路，所以Tij 不一定等于 Tji。

在时间 0 的时候，小明在 1 号商店，开始了收集礼物的旅程。请你帮他设计一条路线来获得尽可能多的礼物。 $1 \le N \le 400$ $0 \le P_i \le 10^9$ ,$1 \le T_{i,j} \le 10^6$