暂无测试数据。

蒜头君在韭菜老师的带领下学习 OI，韭菜老师的训练方式很奇怪，他会一口气让蒜头君做很多道题，要求他在规定的时间完成。而韭菜老师为了让自己的威信提高，自己也会把这些题都做一遍。蒜头君和韭菜老师都有一个水平值，他们水平值的比值和做这些题所用时间的比值成反比。比如如果蒜头君的水平值是 $1$，韭菜老师的水平值是 $2$，那么蒜头君做同一道题的时间就是韭菜老师的 $2$ 倍。

每个题目有他所属的知识点，这我们都知道，比如递归，动规，最短路，网络流……这里我们不考虑这些事情，我们只知道他们分别是知识点 $1$，知识点 $2$……

每一个同一知识点下的题目，对于蒜头君来讲，都是一样难的。做出每一道题，韭菜老师都有其独特的奖励值，而奖励值和题目的知识点没有必然联系。现在蒜头君同学请你帮忙计算，在韭菜老师规定的时间内，他所能得到最大奖励值是多少。

输入格式

第一行两个整数 $K_1,K_2$，分别表示蒜头君和韭菜老师的水平值。

第二行两个整数 $m,n$，分别表示题目总数和知识点总数。

第三行 $n$ 个整数 $t_i$，表示韭菜老师做每个知识点所花的时间。

接下来 $m$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 题的知识点编号和做出该题的奖励。

最后一行一个整数 $T$，表示规定的时间。

输出格式

一个整数，表示蒜头君能获得的最大奖励。

数据范围

$1\ \le K_1 \le K_2 \le 10000$，$K_2$ 是 $K_1$ 的整数倍，$1\le n,m,T,t_i \le 5000$，$1 \le x_i \le n$，$1\le y_i \le 10^4$。

1 2
5 4
3 4 5 4
3 2
3 3
4 1
2 2
1 1
26

6