A. The Contest

Codeforces

IDCF813A

Time2000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

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! 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.** 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_. 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. ## Input 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. 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. **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.** ## Output 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. Otherwise print "-1" (without brackets). [samples] ## Note 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. In the second example Pasha invents the solution only after the website stops working for the last time. In the third example Pasha sends the solution exactly at the end of the first period.

Pasha 正在参加一个知名网站上的竞赛。这一次，他想赢得比赛，会不择手段争取第一名！本次竞赛包含 #cf_span[n] 道题目，Pasha 解决第 #cf_span[i] 道题需要 #cf_span[ai] 个时间单位（他的解答总是正确的）。在任意时刻，他只能思考一道题的解法（即他不能同时解决两道题）。Pasha 发送解答所花费的时间可忽略不计。*Pasha 可以在同一时刻发送任意数量的解答。* 不幸的是，由于参赛者太多，网站并不总是正常运行。Pasha 收到信息，网站仅在 #cf_span[m] 个时间段内可用，第 #cf_span[j] 个时间段由其起始时刻 #cf_span[lj] 和结束时刻 #cf_span[rj] 表示。当然，Pasha 只能在网站运行时发送解答。换句话说，Pasha 可以在时刻 #cf_span[T] 发送解答，当且仅当存在某个时间段 #cf_span[x] 满足 #cf_span[lx ≤ T ≤ rx]。 Pasha 希望知道他能取得的最好成绩。我们需要告诉他，如果他采取最优策略，他能够提交所有题目解答的最早时刻；如果无论如何都无法完成，则输出不可能。第一行包含一个整数 #cf_span[n (1 ≤ n ≤ 1000)] —— 题目数量。第二行包含 #cf_span[n] 个整数 #cf_span[ai (1 ≤ ai ≤ 105)] —— Pasha 解决第 #cf_span[i] 道题所需的时间。第三行包含一个整数 #cf_span[m (0 ≤ m ≤ 1000)] —— 网站可运行的时间段数量。接下来的 #cf_span[m] 行描述这些时间段。第 #cf_span[j] 行包含两个数 #cf_span[lj] 和 #cf_span[rj (1 ≤ lj < rj ≤ 105)] —— 第 #cf_span[j] 个时间段的起始和结束时刻。 *保证这些时间段互不重叠，且按时间顺序给出，因此对于每个 #cf_span[j > 1]，满足条件 #cf_span[lj > rj - 1]。* 如果 Pasha 能在比赛结束前解决并提交所有题目，请输出他能提交所有解答的最小时刻；否则输出 "-1"（不含引号）。在第一个例子中，Pasha 可以这样操作：他用 4 个时间单位解决第二题，并立即发送；然后用 3 个时间单位解决第一题，并在比赛开始后第 7 个时间单位发送，因为此时网站再次开始运行。在第二个例子中，Pasha 直到网站最后一次停止运行后才完成解答。在第三个例子中，Pasha 恰好在第一个时间段结束时发送解答。 ## Input 第一行包含一个整数 #cf_span[n (1 ≤ n ≤ 1000)] —— 题目数量。第二行包含 #cf_span[n] 个整数 #cf_span[ai (1 ≤ ai ≤ 105)] —— Pasha 解决第 #cf_span[i] 道题所需的时间。第三行包含一个整数 #cf_span[m (0 ≤ m ≤ 1000)] —— 网站可运行的时间段数量。接下来的 #cf_span[m] 行描述这些时间段。第 #cf_span[j] 行包含两个数 #cf_span[lj] 和 #cf_span[rj (1 ≤ lj < rj ≤ 105)] —— 第 #cf_span[j] 个时间段的起始和结束时刻。*保证这些时间段互不重叠，且按时间顺序给出，因此对于每个 #cf_span[j > 1]，满足条件 #cf_span[lj > rj - 1]。* ## Output 如果 Pasha 能在比赛结束前解决并提交所有题目，请输出他能提交所有解答的最小时刻；否则输出 "-1"（不含引号）。 [samples] ## Note 在第一个例子中，Pasha 可以这样操作：他用 4 个时间单位解决第二题，并立即发送；然后用 3 个时间单位解决第一题，并在比赛开始后第 7 个时间单位发送，因为此时网站再次开始运行。在第二个例子中，Pasha 直到网站最后一次停止运行后才完成解答。在第三个例子中，Pasha 恰好在第一个时间段结束时发送解答。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of problems. Let $ A = (a_1, a_2, \dots, a_n) \in \mathbb{Z}^n $ be the sequence of time units required to solve each problem, where $ a_i \geq 1 $. Let $ m \in \mathbb{Z}_{\geq 0} $ be the number of working periods. Let $ P = \{(l_j, r_j) \mid j \in \{1, \dots, m\}\} $ be the set of non-overlapping, chronologically ordered working periods, with $ l_j < r_j $ and $ l_j > r_{j-1} $ for $ j > 1 $. **Constraints** 1. $ 1 \leq n \leq 1000 $ 2. $ 1 \leq a_i \leq 10^5 $ for all $ i \in \{1, \dots, n\} $ 3. $ 0 \leq m \leq 1000 $ 4. For all $ j \in \{1, \dots, m\} $: $ 1 \leq l_j < r_j \leq 10^5 $ 5. Periods are disjoint and sorted: $ l_j > r_{j-1} $ for $ j \geq 2 $ **Objective** Let $ T_{\text{solve}} = \sum_{i=1}^n a_i $ be the total time needed to solve all problems. Pasha may interleave solving and submitting: he can submit any subset of solved problems at any time $ T $ such that $ T \in [l_j, r_j] $ for some $ j $. He must submit *all* solutions by some final time $ T_{\text{final}} $, and wishes to minimize $ T_{\text{final}} $. Find the minimal $ T_{\text{final}} \in \bigcup_{j=1}^m [l_j, r_j] $ such that there exists a schedule where: - The total solving time is $ T_{\text{solve}} $, - Each problem is solved at some time $ s_i \geq \sum_{k=1}^{i-1} a_{\sigma(k)} $ (for some permutation $ \sigma $), - Each solution $ i $ is submitted at time $ t_i \in \bigcup_{j=1}^m [l_j, r_j] $, with $ t_i \geq s_i $, - $ T_{\text{final}} = \max_i t_i $. If no such $ T_{\text{final}} $ exists, output $-1$.

Samples

Input #1

Output #1

Input #2

Output #2

\-1

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "A. The Contest",
    "description": {
      "content": "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! This contest consists of _n_ problems, and Pasha s",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF813A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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!\n\nThis contest consists of _n_ problems, and Pasha s...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Pasha 正在参加一个知名网站上的竞赛。这一次，他想赢得比赛，会不择手段争取第一名！\n\n本次竞赛包含 #cf_span[n] 道题目，Pasha 解决第 #cf_span[i] 道题需要 #cf_span[ai] 个时间单位（他的解答总是正确的）。在任意时刻，他只能思考一道题的解法（即他不能同时解决两道题）。Pasha 发送解答所花费的时间可忽略不计。*Pasha 可以在同一时刻发送任意数量的解...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of problems.  \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}^n $ be the sequence of time units required to solve each problem, where $ a_i ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments