Codah ClubVježbaj. Pošalji. Napreduj.
Prijavi se
Hrvatski
#00065B

Leto - Državno

Catherine loves traveling and she has already started making plans for the upcoming summer. She made a list with n exotic places she would like to visit. For each place it is known how many days she would stay there, we will mark those values as ti, where for each i ≠ j, ti ≠ tj is true.


Catherine has p friends she can travel with. However, not all friends want to go to the same places - instead there are p pairs of integers bi and ei (1 ≤ bi ≤ ei ≤ n). This means that the ith friend wants to go only to the places whose id is j, where bi ≤ j ≤ ei.


Your task is to determine the maximum amount of days Catherine can spend travelling, if the following constraints must be satisfied:


- Catherine can't travel anywhere alone.
- She can visit only one place with each friend.
- She can visit each place only once.


InputFrom the first line of the standard input read the integer n (n ≤ 5.000), the amount of places. From the next line input n integers separated with spaces, those are the values ti (1 ≤ ti ≤ 100.000). The following line contains the integer p (p ≤ 5.000), which represents the amount of friends Catherine has. In each of the next p lines there are two numbers, bi and ei.

OutputWrite to the standard output the maximal amount of days Catherine can spend travelling in total.

Input:
8
2 3 1 4 6 5 20 9
5
5 6
2 5
1 2
8 8
8 8
Output:
23
Explanation: There are 8 places. The time spent on the first place is 2 days, on the second place 3 days, etc. Catherine has 5 friends. The first friend wants to go to place 5 or 6, the second one on one of the following: 2, 3, 4 or 5; etc. The optimal travel would be gained, f.ex., if Catherine goes to the sixth place with the first friend (5 days), to the fifth place with the second friend (6 days), to the second place with the third friend (3 days), and to the eighth place with the fifth friend (9 days). The total traveling time in this case is 5 + 6 + 3 + 9 = 23 days.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.