Problem G
Transit Card

Picture by Cello06 via Wikimedia Commons, cc by

Since you miss your friends back home, you will frequently be going home for a few days. On the one hand, it seems wasteful to pay for keeping the transit card charged during the days you are away. But on the other hand, if you do not keep it charged then you have to start a new date interval when you get back and will be forced to pay the higher price for a few days again.

Given the pricing scheme and the schedule of which days you are going to be away, you decide to write a program to help you determine the cheapest option.

Input

The first line of input contains an integer $1 \le l \le 100$, the number of price levels for the transit card. Then follows a line containing $l$ integers $p_1, p_2, \ldots , p_{l}$, where $1 \le p_ i \le 1\, 000$ is the price per day at the $i^\textrm {th}$ price level. The next line contains $l-1$ integers $d_1, d_2, \ldots , d_{l-1}$, where $1 \le d_ i \le 10^6$ indicates how many days the $i^\textrm {th}$ price level is active. Thus for example the third price level $p_3$ becomes active after $d_1 + d_2$ days. The last price level is active indefinitely. You may assume that the prices are monotonically decreasing, i.e., $p_1 > p_2 > \ldots > p_ l$.

The fourth line of input contains two integers $t$ and $n$, where $1 \le t \le 10^6$ is the total number of days for which you want to buy a transit pass, and $0 \le n \le 5\, 000$ is the number of trips home you make during this period. After this follow $n$ lines, each containing two integers $a$ and $b$ ($1 \le a \le b \le t$), indicating that you will be away on all days from day $a$ to day $b$ (inclusive). The days are numbered from $1$ to $t$. You may assume that the trips home are listed in chronological order and that they do not overlap.

Output

Output the smallest total cost of your transit card for the $t$ days.

3
20 15 10
7 7
30 0

405

3
20 15 10
7 7
30 2
5 5
15 25

345