You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Champion_Q既然成年了，18岁生日的蛋糕当然要有啦，Champion_Q的家里超级有钱，所以他决定办一场轰轰烈烈的生日party，所以他要做很多很多的生日蛋糕来庆祝啦，在仔细思考下，他决定制作n个生日蛋糕，但是每个蛋糕需要花费x点时间，这太慢啦，所以为了尽快的制作完生日蛋糕，Champion_Q请来了南疆最有名的巫师鬼厉，虽然鬼厉身上只有s点法力，但是他有两类神奇的法术，第一类法术有m种，每种法术可以将制作每个蛋糕的时间变成a[i]，但是需要花费b[i]点法力，第二类法术有k种，每种法术可以瞬间制作c[i]个蛋糕，但是需要花费d[i]点法力，当然了，每类法术中鬼厉先生只能使用一种且每类法术最多只能使用一次，Champion_Q有钱任性，不在乎消耗,他只想以最快的速度做出来所有的蛋糕

Input

第一行包括n,m,k(1≤n≤2·10^9,1≤m,k≤2·10^5) ,分别代表蛋糕数量，第一类法术包含的法术有多少种，第二类法术包含的法术有多少种；第二行包括x,s(2 ≤ x ≤ 2·10^9, 1 ≤ s ≤ 2·10^9)，分别代表刚开始制作一个魔法蛋糕需要花费的时间和鬼厉法师身上的初始法力值，第三行第四行都包括m个数，分别代表a[i]和b[i] (1 ≤ a[i] < x,1 ≤ b[i] ≤ 2·10^9)，第五行第六行都包括k个数，分别表示c[i]和di，为了减小题目难度，我们规定，c,d两个数组均为非严格递增的

Output

输出一行，代表做完这些蛋糕需要的最少时间（温馨小提示，可以不使用任何法术哦）

Samples

10 3 3

10 33

1 7 6

17 25 68

2 9 10

78 89 125

10

Limitation

1s, 1024KiB for each test case.