Lj 的朋友 WKY 是一名神奇的少年，在同龄人之中有着极高的地位。。。

他的老师老王对他的程序水平赞叹不已，于是下决心培养这名小子。

老王的训练方式很奇怪，他会一口气让 WKY 做很多道题，要求他在规定的时间完成。而老王为了让自己的威信提高，自己也会把这些题都做一遍。

WKY 和老王都有一个水平值，他们水平值的比值和做这些题所用时间的比值成反比。比如如果 WKY 的水平值是 1，老王的水平值是 2，那么 WKY 做同一道题的时间就是老王的 2 倍。

每个题目有他所属的知识点，这我们都知道，比如递归，动规，最短路，网络流。在这里我们不考虑这些事情，我们只知道他们分别是知识点 1，知识点 2……每一个知识点有他对应的难度，比如动态规划经常难于模拟。

而每一个同一知识点下的题目，对于 WKY 来讲，都是一样难的。而做出每一道题，老王都有其独特的奖励值。而奖励值和题目的知识点没有必然联系。

现在 WKY 同学请你帮忙，计算在老王规定的时间内，WKY 所能得到最大奖励值是多少 。

第一行：

WKY 的水平值和老王的水平值。

数据保证 WKY 的水平值小于老王的水平值（哪怕它不现实），且老王的水平值是 WKY 的水平值的整数倍。

第二行：

题目的总数 m 和知识点的总数 n。

第三行：

n 个整数。第 i 个整数表示老王在做第 i 个知识点的题目所需的时间。

接下来有 m 行数每一行包括两个整数 p，q 。p 表示该题目所属的知识点，q 表示该题目对应的奖励值。

最后一行是规定的时间。

输出文件只有一行，表示能到得到的最大奖励值。

对于 100 \% 的数据，1 \leq n, m \leq 100，规定时间 \leq 5000。1 \leq p \leq n，1 \leq q \leq 1000。

luogu