该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

歌仙之章★★★☆

动身吧旅行者，佚失的诗篇还在等待我们呢

题目描述

温迪酷爱饮酒，其次便是诗歌。一天，温迪听说果酒湖下藏着丰富的佳酿与诗篇，于是欣然前往，踏上了旅途。

然而这会儿，他遇上了一点麻烦。他的面前是一个大的密室，密室被分成了$n * m$的小房间，每个小房间里都将会有一只魔物看守，部分房间还会有诗或酒，每个房间只与边上的四个房间相连。在进入密室前，温迪会将体力恢复至最大值$M$，并从左上角的房间$(1,1)$进入，密室的出口在右下角$(n,m)$。

温迪的体力规则如下：

1. 温迪每次移动，即从一个房间转移至与该房间相邻的房间，损失$1$点体力，进入和离开密室也会。
2. 温迪每次遇到魔物，都会将该魔物清除，并损失$1$点体力。
3. 温迪每获得一瓶酒，恢复体力$k_1$点。
4. 温迪每获得一篇诗，恢复体力$k_2$点。
5. 温迪的体力不能超过其最大体力$M$(可以等于)，如果体力大于了最大体力$M$，那么体力直接取$M$。
6. 任意过程中，当温迪的体力为负数时，视为无法离开密室。体力为$0$不视为无法离开。
7. 所有体力的增加在减少之后结算。

为了能够应对密室后面未知的危机，请你帮助温迪计算，他离开出口时最多可以剩下多少体力。如果无法离开密室，请输出$-1$.

说明：

例一. 最大体力$M = 9$，房间$R$中有一篇诗（可以恢复体力$2$点）。如果进入房间前剩余体力$9$点，那么先进入房间变成$8$点，再清除魔物变成$7$点，然后恢复体力变成$9$点。

例二.最大体力$M = 9$，房间$R$中有一篇诗（可以恢复体力$2$点）。如果进入房间前剩余体力$1$点，那么先进入房间变成$0$点，此时不视为失败，再清除魔物变成$-1$点，此时应当视为失败。

数据格式

输入

第一行，5个正整数$n,m,M,k_1,k_2$如题意。（其中$n$为行数，$m$为列数）

接下来一行，一个正整数$s_1$，表示酒的数量。然后$s_1$行，每行两个正整数$a,b$，表示位置$(a,b)$处有一瓶酒。

接下来一行，一个正整数$s_2$，表示诗的数量。然后$s_2$行，每行两个正整数$a,b$，表示位置$(a,b)$处有一篇诗。

输出

温迪离开出口时可以剩下体力可能的最大值。如果无法离开密室，输出-1.

样例

输入

3 4 10 1 2
2
1 2
2 3
1
3 4

输出

1

样例解释

数据范围及约定

测试点编号	约定	测试点分值
$1$	$n=1$，且诗与酒不会出现在同一个位置	每个测试点$10$分
$2$	$m=1$，且诗与酒不会出现在同一个位置	每个测试点$10$分
$3,4$	$2 \le n,m \le 100$，且诗与酒的数量均为$0$	每个测试点$10$分
$5$~$10$	没有额外限制	每个测试点$10$分

对于所有数据$1 \le n,m \le 300$，$1 \le a \le n$，$1 \le b \le m$，$1 \le M \le 5000$，$0\le s_1,s_2 \le 5000$，$0 \le k_1,k_2 \le 5000$.