codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

813A.md (3056B)


      1 Source: https://codeforces.com/problemset/problem/813/A
      2 
      3 A. The Contest
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Pasha is participating in a contest on one well-known website. This time he wants to win the contest and will do anything to get to the first place!
     22 
     23 This contest consists of *n* problems, and Pasha solves *i*th problem in *a**i* time units (his solutions are always correct). At any moment of time he can be thinking about a solution to only one of the problems (that is, he cannot be solving two problems at the same time). The time Pasha spends to send his solutions is negligible. Pasha can send any number of solutions at the same moment.
     24 
     25 Unfortunately, there are too many participants, and the website is not always working. Pasha received the information that the website will be working only during *m* time periods, *j*th period is represented by its starting moment *l**j* and ending moment *r**j*. Of course, Pasha can send his solution only when the website is working. In other words, Pasha can send his solution at some moment *T* iff there exists a period *x* such that *l**x* ≤ *T* ≤ *r**x*.
     26 
     27 Pasha wants to know his best possible result. We need to tell him the minimal moment of time by which he is able to have solutions to all problems submitted, if he acts optimally, or say that it's impossible no matter how Pasha solves the problems.
     28 
     29 Input
     30 
     31 The first line contains one integer *n* (1 ≤ *n* ≤ 1000) — the number of problems. The second line contains *n* integers *a**i* (1 ≤ *a**i* ≤ 105) — the time Pasha needs to solve *i*th problem.
     32 
     33 The third line contains one integer *m* (0 ≤ *m* ≤ 1000) — the number of periods of time when the website is working. Next *m* lines represent these periods. *j*th line contains two numbers *l**j* and *r**j* (1 ≤ *l**j* < *r**j* ≤ 105) — the starting and the ending moment of *j*th period.
     34 
     35 It is guaranteed that the periods are not intersecting and are given in chronological order, so for every *j* > 1 the condition *l**j* > *r**j* - 1 is met.
     36 
     37 Output
     38 
     39 If Pasha can solve and submit all the problems before the end of the contest, print the minimal moment of time by which he can have all the solutions submitted.
     40 
     41 Otherwise print "-1" (without brackets).
     42 
     43 Examples
     44 
     45 Input
     46 
     47 ```
     48 2  
     49 3 4  
     50 2  
     51 1 4  
     52 7 9
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 7
     59 ```
     60 
     61 Input
     62 
     63 ```
     64 1  
     65 5  
     66 1  
     67 1 4
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 -1
     74 ```
     75 
     76 Input
     77 
     78 ```
     79 1  
     80 5  
     81 1  
     82 1 5
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 5
     89 ```
     90 
     91 Note
     92 
     93 In the first example Pasha can act like this: he solves the second problem in 4 units of time and sends it immediately. Then he spends 3 time units to solve the first problem and sends it 7 time units after the contest starts, because at this moment the website starts working again.
     94 
     95 In the second example Pasha invents the solution only after the website stops working for the last time.
     96 
     97 In the third example Pasha sends the solution exactly at the end of the first period.