{"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 Point $x_i$, and can be sold for $s_i$ yen (the currency of Japan) if captured.\nYou 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.\nWhat is the maximum profit that can be earned by throwing a net only once?\n\n## Constraints\n\n*   $1 ≤ N ≤ 2 × 10^5$\n*   $1 ≤ x_1 < x_2 < ... < x_N ≤ 10^{15}$\n*   $1 ≤ s_i ≤ 10^9$\n*   All input values are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$x_1$ $s_1$\n$x_2$ $s_2$\n$:$\n$x_N$ $s_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"relay2_f","tags":[],"sample_group":[["5\n10 20\n40 50\n60 30\n70 40\n90 10","90\n\nIf 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."],["5\n10 2\n40 5\n60 3\n70 4\n90 1","5\n\nThe 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."],["4\n1 100\n3 200\n999999999999999 150\n1000000000000000 150","299"]],"created_at":"2026-03-03 11:01:14"}}