你正在计划一次公路旅行。你已经仔细规划了所有可能停留的路径点。从每个路径点出发，都有通往其他路径点的道路，但这些道路只能单向通行。为了缓解交通拥堵，道路规划者决定对较热门的道路收取通行费。而对于较冷门的道路，甚至会支付费用让你通行。

因此，这次公路旅行有可能获得利润。但有一个限制——你的钱包里最多只能比出发时多出 $w$ 美元。即使你的钱包已满，你仍然可以获得报酬，但你无法保留超过出发时金额 $w$ 美元以上的收益。你可以假设在需要支付通行费时，你总是有足够的钱来支付。

请问你在旅途中能获得的最大利润是多少？

输入格式

输入的第一行包含三个整数 $n, m$ 和 $w$ ($1 \le n, m \le 2000, 1 \le w \le 100$)，其中 $n$ 是路径点的数量，$m$ 是道路的数量，$w$ 是你钱包的额外容量。路径点编号为 $1$ 到 $n$。第一个路径点 ($1$) 是你公路旅行的起点，最后一个路径点 ($n$) 是目的地。

接下来的 $m$ 行，每行包含三个整数 $u, v$ 和 $t$ ($1 \le u, v \le n, -100 \le t \le 100$)，表示有一条从路径点 $u$ 到路径点 $v$ 的道路，收益为 $t$ 美元。如果 $t > 0$，则你使用该道路会获得 $t$ 美元的报酬。如果 $t < 0$，则你必须支付 $|t|$ 美元的通行费，这会导致你的利润发生 $t$ 的变化。保证 $u \neq v$，且从 $u$ 到 $v$ 最多只有一条道路（但可能存在从 $v$ 到 $u$ 的道路）。

你可以假设从路径点 $1$ 到达路径点 $n$ 是可能的。

输出格式

输出一个整数，表示你在公路旅行中能获得的最大利润。如果存在亏损，请将亏损作为负数输出。

样例

输入 1

4 4 9
1 2 5
1 3 -2
2 4 1
3 4 10

输出 1

8

输入 2

4 4 7
1 2 5
1 3 -2
2 4 1
3 4 10

输出 2

7

输入 3

3 3 5
1 3 -10
3 2 2
2 3 -1

输出 3

4