U440683 流浪旅客

在广袤的N国大地上，有一位放荡不羁的流浪旅客小Z，他热衷于探索未知，渴望在旅途中找到属于自己的自由与真谛。然而，这片土地并非一片祥和，旅途中充满了未知的危险与挑战。流浪旅客需要凭借自己的智慧和勇气，克服重重困难，完成他的冒险之旅。 [小Z](https://image.so.com/view?q=%E6%B5%81%E6%B5%AA%E8%80%85%E5%8E%9F%E7%A5%9E&src=tab_www&correct=%E6%B5%81%E6%B5%AA%E8%80%85%E5%8E%9F%E7%A5%9E&ancestor=list&cmsid=95bf9ada7d764036d05ff96fac508f9e&cmras=6&cn=0&gn=0&kn=0&crn=0&bxn=0&fsn=60&cuben=0&pornn=0&manun=0&adstar=0&clw=263#id=4310ead5b074efa2e7549eb13c9a1aea&currsn=0&ps=73&pc=73)

流浪旅客站在 N 国的起点城市（编号为 $1$），手中握着一张地图，上面标记着 N 国的城市布局和道路关系。每个城市都有着独特的风景和文化，同时也隐藏着各种资源和危险。他的目标是穿越这片土地，尽可能地访问更多的城市，收集更多的资源，同时避免遭遇过多的危险。 地图上标注着每个城市的编号、坐标以及资源值。**资源值可以是正数（表示补给点，可以恢复生命值），可以是负数（表示危险区域，会扣除生命值），也可以是 $0$（表示普通城市）。流浪旅客的初始生命值有限，且不能收集起点的资源，** 他需要在旅途中不断寻找补给点来恢复生命值，同时避免进入危险区域。 城市之间通过单向道路相连，每条道路都有一个通行时间 $t$。流浪旅客需要选择合适的道路来规划他的路线，以在有限的时间内尽可能多地访问城市并收集资源。 现在，请你帮助这位流浪旅客制定一个策略，以在限定时间内尽可能多地访问城市并收集资源，同时保证生命值不低于 $0$。

第一行三个整数 $N$、$M$ 和 $T$，分别表示城市的数量、道路的数量和流浪旅客拥有的总时间。 接下来 $N$ 行，每行包含一个整数 $v$ 表示资源值，$v$（$v>0$ 表示补给点，增加生命值；$v

输出两行，第一行一个整数 $q$，表示流浪旅客在限定时间内能够访问的最多城市数量。如果无法在规定时间内访问任何城市，仅有起点，输出 $1$。 第二行输出最后的生命值。 ### **第一目标是多去城市，并不是多赚生命值！**

## 提示 **样例解释** 1. 从 $1$ 号城市到 $4$ 号城市，时间 1，生命加 30； 2. 从 $4 \to 3$，时间 1，生命减 10； 3. 从 $3 \to 5$，时间 4，生命不变。 最后时间为 $1+1+4=6$，可行。 最后生命值为 $100+30-10=120$。 **数据范围** $1 \le N,M,T \le 200;1 \le v \le 10^6;1 \le t \le 10;1 \le T \le 200。$