马克和他的船员正在横渡风神海(在希腊神话中,风神是风的守护者)。他们有一张代表 $$$N$$$x$$$M$$$ 矩阵的地图,其中包含陆地和海洋领域,并且他们想要到达港口(港口被视为海洋领域)。他们很匆忙,因为那里的风非常强而且多变,他们的食物只能在海上$$$K$$$天使用(这是他们在船上可以携带的最大数量)。马克船员中的约翰知道如何每天预测 $$$W$$$ 天的风向,这足以让他们到达港口或耗尽食物。马克可以在一天内将船向四个方向(北、东、南、西)移动一格,但他也可以留在同一个地方。风可以向四个方向吹(北、东、南、西),或者当天不吹。风神海上的风如此之大,以至于船只向风吹的方向移动了整整一格。船舶产生的运动是船舶作用和当天风力的总和。马克必须小心,以便让船保持在海上,由此产生的运动必须在海场结束,并且必须有一条从起始场穿过大海的 4 条连接路径。四连接路径是一条路径,只有当它们共享一侧时,您才能从一个单元格到达另一个单元格。
例如,在下图中,由于没有穿过大海的 4 条连接路径,因此船舶无法移动到港口。
在下图中,船舶可以移动到港口,因为有一条穿过大海的 4 条连接路径,如红色箭头所示。此外,如果发生下列情况之一,船舶可以一举移至港口。风向东吹,马克将船向北移动,或者风向北吹,马克将船向东移动。在这两种情况下,船舶最终都会一次到达港口。
马克还必须将船保留在地图上,因为他不知道外面是什么。对于马克和他的船员来说幸运的是,海上有$$$T$$$鱼店,他们可以在那里最大限度地补充食物供应,但每个鱼店只营业一天。这意味着马克和他的工作人员必须在确切的工作日到达商店的位置才能补充食物供应。帮助马克找到他和他的船员到达港口所需的最短天数,或者打印 $$$-1$$$(如果他们拥有的食品供应不可能做到这一点)。
输入
第一行包含两个整数 $$$N$$$ 和 $$$M$$$ ($$$1 \leq N, M \leq 200$$$) - 表示地图的行数和列数。
第二行包含三个整数,$$$K$$$ ($$$0 \leq K \leq 200$$$) 是可用粮食供应的天数,$$$T$$$ ($$$0 \leq T \leq 20$$$) 是具有额外粮食供应的田地数量,$$$W$$$ ($$$0 \leq W \leq 10^6$$$) 这是有风信息的天数。
接下来是 $$$N$$$x$$$M$$$ 字符矩阵,其中填充了“L”、“S”、“P”或“M”的值。 “L”代表陆地,“S”代表海洋部分。 “P”代表港口字段,“M”代表船舶的起始字段。
下一行包含 $$$W$$$ 字符,其中包含每天的风向信息。可能的输入为“N”- 北、“S”- 南、“E”- 东、“W”- 西和“C”- 无风。如果马克的船员能够到达港口,那么保证他们不需要超过 $$$W$$$ 天即可到达。
最后有$$$T$$$ 行与食品供应位置。每行包含三个整数,$$$Y_i$$$ 和 $$$X_i$$$ ($$$0 \leq Y_i < N, 0 \leq X_i < M$$$) 表示食物供应的坐标(Y 是行号,X 是列号),$$$F_i$$$ ($$$0 \leq F_i \leq 10^6$$$) 表示从开始日期算起的天数。食物供应充足。
输出
一个整数,表示到达港口的最短天数,如果不可能,则为 $$$-1$$$。
示例
输入 #1
3 3 5 2 15 M S S S S S S S P S W N N N N N N N N N N N N N 2 1 0 1 2 0
输出 #1
-1
输入 #2
3 3 5 2 15 M S S S S S S S P S E N N N N N N N N N N N N N 2 1 0 1 2 0
输出 #2
2
输入 #3
5 5 4 1 15 M S S S S S S S S L S S S L L S S S S S S S S S P C C C C S S E E C C C C C C C 0 1 4
输出 #3
8