你在一片 $N\times M$ 的海洋上行船。

你的船每次最多只能携带支持 $K$ 天的食物，每天你可以向上下左右行进一格（也可以不移动），然后这一天结束。每一天都需要消耗一天的食物（无论移不移动）。

但是在这 $W$ 天中，每天可能有风（也可能没风），如果有风，那么船会在你的移动之后再被风吹，向当天风向移动一格，两个操作叠加起来才是你当天的移动。

你能够到达一个位置当且仅当这个位置不是陆地且能够与起点四连通，并且能够按照 先被风吹在行动/先行动在被风吹 的顺序，在不经过陆地的情况下到达目的地。

你需要保证一天结束的时候仍然在地图内，并且在食物耗尽之前到达港口。

但是在海上有 $T$ 个鱼市。这些鱼市可以给你的船补满食物，但是第 $i$ 个鱼市只会在 $F_i$ 当天开放，也就是说，如果你想要补充食物，就必须在鱼市开放当天处于鱼市开放位置。

如果能够到达港口，请输出最少的天数，否则输出 $-1$。

数据保证，如果能够到达港口，那么最少的天数一定 $\le W$

$N,M\le 200,0\le K\le 200,0\le T\le 20,0\le W,F_i\le 10^6$

By:Call_me_Eric

你在一片 $N\times M$ 的海洋上行船。

你的船每次最多只能携带支持 $K$ 天的食物，每天你可以向上下左右行进一格（也可以不移动），然后这一天结束。每一天都需要消耗一天的食物（无论移不移动）。

但是在这 $W$ 天中，每天可能有风（也可能没风），如果有风，那么船会在你的移动之后再被风吹，向当天风向移动一格，两个操作**叠加**起来才是你当天的移动。

你能够到达一个位置当且仅当这个位置不是陆地且能够与起点四连通，并且能够按照 先被风吹在行动/先行动在被风吹 的顺序，在不经过陆地的情况下到达目的地。

你需要保证一天结束的时候仍然在地图内，并且在食物耗尽之前到达港口。

但是在海上有 $T$ 个鱼市。这些鱼市可以给你的船补满食物，但是第 $i$ 个鱼市只会在 $F_i$ 当天开放，也就是说，如果你想要补充食物，就必须在鱼市开放当天处于鱼市开放位置。

如果能够到达港口，请输出最少的天数，否则输出 $-1$。

数据保证，如果能够到达港口，那么最少的天数一定 $\le W$

$N,M\le 200,0\le K\le 200,0\le T\le 20,0\le W,F_i\le 10^6$

By:Call_me_Eric