Capture

AtCoder

IDrelay2_f

Time2000ms

Memory256MB

Difficulty—

In a long narrow forest stretching east-west, there are $N$ beasts. Below, we will call the point that is $p$ meters from the west end Point $p$. The $i$\-th beast from the west $(1 ≤ i ≤ N)$ is at Point $x_i$, and can be sold for $s_i$ yen (the currency of Japan) if captured. You will choose two integers $L$ and $R$ $(L ≤ R)$, and throw a net to cover the range from Point $L$ to Point $R$ including both ends, $[L, R]$. Then, all the beasts in the range will be captured. However, the net costs $R - L$ yen and your profit will be $($the sum of $s_i$ over all captured beasts $i) - (R - L)$ yen. What is the maximum profit that can be earned by throwing a net only once? ## Constraints * $1 ≤ N ≤ 2 × 10^5$ * $1 ≤ x_1 < x_2 < ... < x_N ≤ 10^{15}$ * $1 ≤ s_i ≤ 10^9$ * All input values are integers. ## Input Input is given from Standard Input in the following format: $N$ $x_1$ $s_1$ $x_2$ $s_2$ $:$ $x_N$ $s_N$ [samples]

Samples

Input #1

Output #1

90

If you throw a net covering the range $[L = 40, R = 70]$, the second, third and fourth beasts from the west will be captured, generating the profit of $s_2 + s_3 + s_4 - (R - L) = 90$ yen. It is not possible to earn $91$ yen or more.

Input #2

Output #2

5

The positions of the beasts are the same as Sample 1, but the selling prices dropped significantly, so you should not aim for two or more beasts. By throwing a net covering the range $[L = 40, R = 40]$, you can earn $s_2 - (R - L) = 5$ yen, and this is the maximum possible profit.

Input #3

4
1 100
3 200
999999999999999 150
1000000000000000 150

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Capture",
    "description": {
      "content": "In a long narrow forest stretching east-west, there are $N$ beasts. Below, we will call the point that is $p$ meters from the west end Point $p$. The $i$\\-th beast from the west $(1 ≤ i ≤ N)$ is at Po",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "relay2_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In a long narrow forest stretching east-west, there are $N$ beasts. Below, we will call the point that is $p$ meters from the west end Point $p$. The $i$\\-th beast from the west $(1 ≤ i ≤ N)$ is at Po...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments