Luogu侧点这里

题目背景

书接上回，tiger的朋友输了太多把游戏，想报复tiger（？

一天，tiger又在机房打电动了（什），同学就安装了一个定时拍照的相机，用来收集tiger打电动的证据

（危 tiger 危）

题目描述

tiger 会在$x$个时间区间中打游戏(包括上界下界) 而相机是 在$y$个时间点 拍照

如果拍照的时候tiger正在打游戏，那么证据就会+1 今天老师布置了$n$道题目，第$i$道题需要$a[i]$分钟可以完成，大家至少要做$m$道题

而屑tiger每被发现一次，就需要多做一题(惩罚太轻了(什)) 但是tiger可以选择使用Ctrl+C/V让一题的时间变为$0$，但是这个技能最多使用2次

因为只要用了第3次他的名字就会变成：$\color{#996600}\text{tiger2008}\rule[-2pt]{31pt}{12pt}$$\kern{-29pt}\color{white}\small 作弊者$

现在屑tiger已经被发现了，他找到了认真学习的神牛你来帮忙算一算他需要多少时间完成

输入格式

第1行输入两个数$x,y$，代表tiger玩游戏区间和同学的拍照时间点数

第2~x+1行，每行输入两个数$u[i],v[i]$，代表第$i$个区间开始时间和结束时间

然后输入一行$y$个数，第$i$个数$t[i]$代表相机在这个时间点拍照

接下来输入两个数$n,m$，表示有n道题，至少做m道 最后输入n个数，第$i$个数$a[i]$表示第$i$道题需要的时间

输出格式

输出一个数，代表tiger需要的最短时间

样例 #1

样例输入 #1

4 3
1 2
3 4
6 10
15 90
3 5 20
8 2
1 5 2 3 7 6 4 8

样例输出 #1

3

提示

数据保证区间从左到右读入且不重叠，拍照时间从左到右 因为tiger和同学只会C++，所以行末有空格(?)

样例解释

同学第一次和第三次拍照拍到了tiger，加上原先2题需要做4题

tiger用复制粘贴解决2题，剩下时间最小的2题是1+2=3

数据范围

对于$30\%$的数据，$3\leq x,y,n,m\leq100$

对于$50\%$的数据，$3\leq x,y,n,m\leq10^3$

对于$70\%$的数据，$3\leq x,y,n,m\leq10^4$

对于$100\%$的数据，$3\leq x,y,n,m\leq10^5$，$m+y\leq n$，$1\leq u[i],v[i],a[i]\leq10^6$