#P2083. 找人

找人

题目描述

小明要到他的同学家玩,可他只知道他住在某一单元,却不知住在哪个房间。那个单元有 nn 层(1,2,,n1,2,\ldots,n),每层有 mm1,2,,m1,2,\ldots,m)个房间。

小明会从第一层的某个房间开始找,他找的方式也很特别,每次到了一个房间,如果不是他的同学,他就会询问这个人,然后他就会去那人告诉他的房间号,如果还不是,他就会继续按这个方法找下去,直到找到。当然,他也有可能找不到同学。他的体力也是有限的,他每爬一层楼梯就会消耗 vv 体力值。你的任务就是求找到同学耗费的最少体力值,如果找不到,就输出 impossible

输入格式

第一行有五个整数,分别代表 nnmmvvxxyyxxyy 表示同学只在 xxyy 房间)。

2n+12\sim n+1 行,每行 m×2m\times 2 个数字,第 i+1i+1j×21j\times2-1 个数 aka_k 和第 j×2j\times2 个数 ak+1a_{k+1} 表示住在 iijj 房间的人提供的信息是 aka_k 层和 ak+1a_{k+1} 房间。(同学的信息就是自己的房间号。)

输出格式

一个数,即答案。

3 3 2 2 3
1 3 3 3 2 1
2 3 1 1 2 3
1 1 1 2 2 3
2

提示

数据规模与约定

对于 100%100\% 的数据,1n10001 \leq n\le10001m1001 \leq m\le1001v501 \leq v\le50