暂无测试数据。

还记得，那一天，你和我肩并着肩。

你喜欢我，我喜欢你。

我们过着两个人的生活。

直到某一天，你走了。

我即使跋山涉水，

也要找到你。

题目描述

小花狗是个旅行家，到喵星球去旅行，遇见了小花猫。他们俩一见钟情。不久小花狗旅行去了，留下了一张\(K\times K\)的正方形地图。

小花猫知道，喵星球在地图上\((a,b)\)的点，小花狗的旅行路线是\((x_1,y_1)\to(x_2,y_2)\to\cdots\to(x_n,y_n)\to(x_1,y_1)\to\cdots\)，且他每天走一格。

现在，小花猫有\(m\)喵币。地图告诉她，这块区域一共有三块地貌：平地（用\(\texttt{.}\)表示）、山峰（用\(\texttt{\#}\)表示）、小河（用\(\texttt{=}\)表示）（保证\((a,b),(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)\)均不为\(\texttt{=}\)）。她只能从平地走到平地、从山峰走到山峰或从平地走到山峰，但必须是上下左右相邻。每一次行走都耗费她一天的时间。如果她迫不得已要从山峰走到平地，可以把面前的平地进行开山操作，时间忽略不计，但是需支付\(\alpha\)喵币。小河上有渡轮。小花猫可以随意从山峰或平地走到小河，并支付\(\beta\)喵币坐渡轮。每一次坐渡轮，小花猫都得选择一个方向（上下左右）并用这个方向一直行驶到头，每行驶一格都耗时一天。到头后，有两种选项可供选择：

• 在上下左右任意一个平地上上岸。
• 另外选择一个方向继续坐渡轮，另付\(\beta\)喵币。

帮小花猫设计一个合理的方案，使得她和小花狗正好相遇。

输入格式

第一行，输入\(n,m,K,a,b,\alpha,\beta\)。

再输入\(2n\)个数，表示小花狗的行程。

接着输入一个\(K\times K\)的字符矩阵代表地图。

输出格式

• 若有可行方案：

  最小化出行的时间。如有多组解，最大化剩余的喵币。分别输出出行的时间和剩余的喵币。

• 若喵币不足：

  先输出\(\texttt{No money!}\)，再输出最小需要借的喵币。

• 若无可行方案：

  直接输出\(\texttt{Impossible!}\)并结束程序。

输入样例 #1

2 100 4 1 1 1000000 10
1 4 3 3
.==.
====
==#=
====

输出样例 #1

3
90

输入样例 #2

2 100 4 1 1 1000000 1000
1 4 3 3
.==.
====
==#=
====

输出样例 #2

No money!
900

输入样例 #3

2 0 4 1 1 0 0
2 2 3 3
.===
=.==
==#=
====

输出样例 #3

Impossible!

数据范围

对于\(50\%\)的数据除\(m,\alpha,\beta\)所有数小于等于\(10\)。

对于\(100\%\)的数据除\(m,\alpha,\beta\)所有数小于等于\(100\)，且\(m,\alpha,\beta\leq10^{18}\)。