D - Disciple Life is Hard / 弟子はつらいよ

Story

Dのひとはドーナツを愛してやまない。常にドーナツを欲している。しかし、師匠であるぶなしめじたんに体を鍛えることを命じられたDのひとは、摂取カロリーを制限しなければならない。そこでDのひとは基礎代謝も考慮し、その日トレーニングによって消費したカロリーの分までドーナツを食べてもよいことにした。Dのひとはドーナツを愛してやまないとはいえ、好みはあるので、食べるドーナツによって得られる幸福感は変わる。また、その日の体力によって行えるトレーニングも変わってくるため、トレーニングの種類、ドーナツの種類、体力を考慮し、D日間で得られる幸福を最大化することを試みた。

Problem

T種類のトレーニングとN種類のドーナツのデータが与えられる。i番目のトレーニングに必要な体力はe_i、消費カロリーはc_iである。トレーニングは1日にちょうどU種類だけ行わなければならず、同じトレーニングは1日に1度しか行えない。トレーニングに必要な体力の総和はその日の体力以下でなければならない。その日の体力からトレーニングに必要な体力の総和を引いた差分は残った体力となり、翌日に引き継がれる。

j番目のドーナツで得られる幸福度はh_j、摂取カロリーはa_jである。1日に同じドーナツを複数個食べてもよい。1日に得られる幸福は食べたドーナツの幸福度の和である。摂取カロリーの総和はその日のトレーニングによる消費カロリーの総和以下でなければならない。その日のトレーニングによる消費カロリーの総和から摂取カロリーの総和を引いた差分が余った消費カロリーとなるが、これは翌日に引き継がない。

体力の上限はSであり、毎日体力はOだけ回復する。初日の始めの体力はSである。D日間で得られる幸福の和の最大値を求めよ。どうやってもトレーニングをちょうどU回行えない日が生じる場合、-1と出力せよ。

Input

入力は以下の形式からなる。

S T U N O D
e_1 c_1
...
e_T c_T
h_1 a_1
...
h_N a_N

1行目は6つの整数からなり、それぞれ体力の上限S、トレーニングの種類T、1日に行うトレーニングの種類数U、ドーナツの種類N、1日に回復する体力量O、日数Dが空白1文字区切りで並んでいる。 続くT行はトレーニングの情報を表す。 i+1行目(1 \leq i \leq T)は2つの整数からなり、それぞれトレーニングに必要な体力e_i、消費カロリーc_iが空白1文字区切りで並んでいる。 続くN行はドーナツの情報を表す。 j+T+1行目(1 \leq j \leq N)は2つの整数からなり、それぞれ得られる幸福度h_j、摂取カロリーa_jが空白1文字区切りで並んでいる。

制約:

Output

D日間で得られる幸福の総和の最大値を1行に出力せよ。 ただし、どうやってもトレーニングをちょうどU回行えない日が生じる場合、-1と出力せよ。 行の最後では必ず改行を行うこと。

Sample Input 1

10 1 1 1 4 3
6 10
5 8

Sample Output 1

15

1日目は1番目のトレーニングを行い1番目のドーナツを食べることで、体力が残り4、幸福度5を得る。 2日目はまず体力が4回復し、8となる。 1番目のトレーニングを行い1番目のドーナツを食べることで、体力が残り2、幸福度5を得る。 3日目はまず体力が4回復し、6となる。 1番目のトレーニングを行い1番目のドーナツを食べることで、体力が残り0、幸福度5を得る。 よって、3日間合計で幸福15を得る。

Sample Input 2

10 3 2 3 3 2
4 10
3 4
3 5
3 4
4 5
5 7

Sample Output 2

19

1日目に1,3番目とのトレーニングを行うと、体力が残り3、消費カロリーが15となる。 2番目のドーナツを3個食べることで、摂取カロリーが15で幸福が12得られる。 2日目にはまず体力が3回復し、6となる。 2,3番目とのトレーニングを行うと、体力が残り0、消費カロリーが9となる。 1番目のトレーニングだけ行った方が多くのカロリーを消費でき、体力も多く残るが、1日には必ず2種類のトレーニングを行う必要があるため、これはできない。 1,2番目のドーナツを1個ずつ食べると摂取カロリーが9で幸福が7得られる。 2日間の幸福の合計は19となり、これが最大である。

Sample Input 3

10 3 2 3 5 3
4 10
2 2
3 5
4 3
5 4
7 5

Sample Output 3

58

Sample Input 4

10 1 1 1 1 1
13 13
13 13

Sample Output 4

-1

体力の上限が10しかないため、体力が13必要なトレーニングを行うことができない。 よって、1日に行うべきトレーニングの種類数を満たすことができないため、-1を出力する。