题目描述

周末到了，小 Z 和小 Y 准备去野生动物园玩，他们计划坐地铁过去，"列车前方到站 「奥体中心」站，下车的乘客请提前做好准备。「奥体中心站」是换乘站。换成地铁 $6$ 号线的乘客，请在「奥体中心站」下车……"

小 Z 和小 Y 想起了他们刚认识的时光，那时，这里只有两条地铁线路：一条环状线和一条非环状线。

非环状线有 $N$ 站，依次编号为 $1,2,\dots,N$，每从当前车站移动到相邻的一个车站需要花费 A 元；环状线有 $M$ 站，一次编号为 $1,2,\dots,M$，每从当前车站移动到相邻的一个车站需要花费 $B$ 元。对于非环状线，若两个车站编号之差的绝对值为 $1$，则它们相邻；对于环状线，若两个车站编号之差的绝对值为 $1$，则它们相邻，特别地，$1$ 号车站和 $M$ 号车站相邻。

两条线路有且仅有两个换乘站。第一个换乘站用 $(a_1,b_1)$ 描述，表示可以从非环状线的 $a_1$ 号站 免费 移动到环状线的 $b_1$ 号站，反之亦然。第二个换乘站用 $(a_2，b_2)$ 描述，意义与上述类似。

小 Z 在非环状线的 $1$ 号车站，小 Y 在非环状线的 $N$ 号车站，他们每周都要见面。他们可以在任意一个车站见面。小 Y 比较懒，所以如果需要她换乘，那么小 Z 就要额外花费 $K$ 元买一杯柠檬水安慰她。

请求出他们见面的最小花费。

输入格式

第一行，五个整数 $N,M,A,B,K$；

第二行四个整数 $a_1,b_1,a_2,b_2$。

输出格式

一行一个整数表示小 Z 和小 Y 见面的最小总花费。

样例 #1

样例输入 #1

8 10 6 4 7
1 9 7 10

样例输出 #1

10

样例 #2

样例输入 #2

97 92 344117000 737429567 565507129
13 50 44 60

样例输出 #2

29741900670

提示

对于前 $20\%$ 的数据，$N,M,A,B,K \le 10$。

对于前 $40\%$ 的数据，$N,M \le 1,000$。

对于前 $60\%$ 的数据，$N,M \le 10^5$。

对于 $100\%$ 的数据，$10 \le N,M,A,B,K \le 10^9,1\le a_1,a_2\le N, 1\le b_1,b_2\le M,a_1 \neq a_2,b_1 \neq b_2$。