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

歌仙之章★★★☆

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

题目描述

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

然而这会儿，他遇上了一点麻烦。他的面前是一个大的密室，密室被分成了\(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\).