### 问题描述 大雨已经持续了数月。为了拯救这座濒临崩溃的城市，阳菜再一次使用了她的能力让天气放晴，身体的一些部分又变得透明了。远在海外的帆高得知了这一消息，走遍世界各地寻找让阳菜身体复原的方法。他的诚意最终打动了隐居的仙人，送给他一个珍贵的阳光收集瓶，并告诉他：通过收集足量的新鲜阳光，然后洒在阳菜身体透明的部分，消失的部分便会重现。 帆高计划在未来 $s$ 天内收集足够多的阳光带给阳菜，地图上总共有 $n$ 个城市，现在帆高在 $1$ 号城市，阳菜在 $n$ 号城市，有 $m$ 条路径，第$i$ 条路径的定义为：从城市 $u_i$ 到城市 $v_i$ 需要 $w_i$ 天时间。可能存在两条路径 $i,j$，满足 $u_i=u_j,v_i=v_j$。地图上的所有路径构成一张有向无环图。你知道未来 $s$ 天每个城市确切的天气，而在这个天气极度魔幻的世界里，只有晴天和雨天两种，只有在晴天可以收集阳光。 帆高需要收集 $k$ 天量的阳光，他急于和阳菜见面，请问他最少能耗费多少天收集足够的阳光并抵达 $n$ 号城市？ 注意，如果帆高这一天决定收集阳光，他会从日出开始一直收集到日落，这样收集到的阳光算作一天的量，他会在剩下的时间里休息。如果帆高打算离开城市 $u$ 前往城市 $v$ 且车程为 $w$ 天，他会从第 $i$ 天早晨出发，则他会在第 $i+w-1$ 天晚上到达目的地。可以在 $1$ 号和 $n$ 号城市收集阳光。视目前时间为第 $1$ 天早晨日出前。 ### 输入格式 输入第 $1$ 行包含四个正整数 $n,m,s,k$，分别表示城市的个数，路径条数，计划的期限，需要收集阳光的量。 下面 $n$ 行，每行 $s$ 个整数，每个数都为 $0$ 或 $1$，第 $i$ 行的第 $j$ 列为 $0$ 表示城市 $i$ 的第 $j$ 天是雨天，为 $1$ 表示这天是晴天。 下面 $m$ 行，每行读入三个正整数 $u_i,v_i,w_i$，表示第 $i$ 条路径。 ### 输出格式 一行一个整数，表示帆高最少要耗费的天数。 如果无法在计划期限内收集到足够量的阳光并到达城市 $n$，请输出 $-1$。 ### 样例输入 ```text 6 6 6 2 0 0 0 0 1 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 2 1 1 3 1 3 4 1 3 5 2 4 6 1 5 6 1 ``` ### 样例输出 ```text 6 ``` ### 说明 仅有一种方案：第 $1$ 天从城市 $1$ 前往城市 $3$，第 $2$ 天在城市 $3$ 收集阳光，第 $3,4$ 天从城市 $3$ 前往城市 $5$，第 $5$ 天在城市 $5$ 收集阳光，第 $6$ 天从城市 $5$ 前往城市 $6$，需要花费 $6$ 天。 ### 评测数据规模 对于 $30$% 的评测数据，满足 $1$ 号城市在未来 $s$ 天都是晴天。 对于 $100$% 的评测数据，$1\leq n,m,k,s \leq 10^3$，$1 \leq u,v \leq n$。