Hide

Problem G
Transit Card

/problems/transitcard/file/statement/en/img-0001.jpg
Picture by Cello06 via Wikimedia Commons, cc by
Having just moved to Transylvania, one of the first orders of business is to get a transit card for the public transportation. The transit card can be charged with intervals of dates. For each such interval, the first few days come at a pretty high price per day, the next few days come at a slightly lower price per day, and so on.

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 1l100, the number of price levels for the transit card. Then follows a line containing l integers p1,p2,,pl, where 1pi1000 is the price per day at the ith price level. The next line contains l1 integers d1,d2,,dl1, where 1di106 indicates how many days the ith price level is active. Thus for example the third price level p3 becomes active after d1+d2 days. The last price level is active indefinitely. You may assume that the prices are monotonically decreasing, i.e., p1>p2>>pl.

The fourth line of input contains two integers t and n, where 1t106 is the total number of days for which you want to buy a transit pass, and 0n5000 is the number of trips home you make during this period. After this follow n lines, each containing two integers a and b (1abt), 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.

Sample Input 1 Sample Output 1
3
20 15 10
7 7
30 0
405
Sample Input 2 Sample Output 2
3
20 15 10
7 7
30 2
5 5
15 25
345
Hide

Please log in to submit a solution to this problem

Log in