{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003e\r\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e// \u003c![CDATA[\r\nMathJax.Hub.Config({tex2jax: {inlineMath: [[\u0027$\u0027,\u0027$\u0027], [\u0027\\\\(\u0027,\u0027\\\\)\u0027]]}});\r\n// ]]\u003e\u003c/script\u003e\r\n\u003cscript src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e\r\n\u003c/p\u003e\r\n\u003cp\u003eThe competition is drawing to a close, and The Team could really use another balloon to help them come out on top...good thing they\u0027re no chumps, and thought of this in advance! Before the contest started, they instructed an accomplice to go to the local balloon shop, buy an extra balloon, and deliver it to them at the conclusion of the event. It is true that their balloons then won\u0027t match up with the scoreboard\u0027s record of which problems they\u0027ve solved - but, in the end, it\u0027s the balloons that count! In fact, The Team knows that, the larger their extra balloon, the more their opponents (and the judges) will be intimidated. They\u0027re not the best ACM-ICPC team in the world for nothing!\u003c/p\u003e\r\n\u003cp\u003eHowever, this balloon shop is rather strange. The accomplice is given an empty balloon (a balloon with size 0), and told that he can tie it closed and keep it after exactly $N$ ($1 \\leq N \\leq 10^6$) minutes. In the meantime, during each minute, an inflation offer is available. If offer $i$ is taken, then, at the start of the $i$th minute, the balloon\u0027s size will be increased by $a_i$ ($0 \\leq a_i \\leq 10^6$). However, since the balloon cannot be closed until the end, its air will leak out at a constant rate, which depends on the gas that was used - in particular, its size will immediately start to decrease at a rate of $d_i$ ($0 \\leq d_i \\leq 10^6$) per minute, until either another offer is taken, or the balloon deflates completely (its size can never become negative, of course).\u003c/p\u003e\r\n\u003cp\u003eThe Team will not be happy if they don\u0027t receive the largest balloon possible. Unfortunately, their accomplice happens to be...you. Can you figure out the maximal size that the balloon can have at the start of minute $N+1$, before it\u0027s too late?\u003c/p\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eFirst line: 1 integer, $N$\u003c/p\u003e\r\n\u003cp\u003eNext $N$ lines: 2 integers, $a_i$ and $d_i$, for $i\u003d1..N$\u003c/p\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003e1 integer, the maximal size which the balloon can have at the start of minute $N+1$.\u003c/p\u003e\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cpre\u003e\u003cstrong\u003eInput:\u003c/strong\u003e\r\n\u003cspan style\u003d\"font-family: \u0027courier new\u0027, courier;\"\u003e5\u003c/span\u003e\r\n\u003cspan style\u003d\"font-family: \u0027courier new\u0027, courier;\"\u003e2 3\u003c/span\u003e\r\n\u003cspan style\u003d\"font-family: \u0027courier new\u0027, courier;\"\u003e10 2\u003c/span\u003e\r\n\u003cspan style\u003d\"font-family: \u0027courier new\u0027, courier;\"\u003e0 1\u003c/span\u003e\r\n\u003cspan style\u003d\"font-family: \u0027courier new\u0027, courier;\"\u003e5 4\u003c/span\u003e\r\n\u003cspan style\u003d\"font-family: \u0027courier new\u0027, courier;\"\u003e1 10\u003c/span\u003e\r\n\r\n\u003cspan style\u003d\"font-weight: bold;\"\u003eOutput:\u003c/span\u003e\r\n\u003cspan style\u003d\"font-family: \u0027courier new\u0027, courier;\"\u003e5\u003c/span\u003e\u003c/pre\u003e\r\n\u003ch3\u003eExplanation of Sample:\u003c/h3\u003e\r\n\u003cp\u003eThe best option is to take only the offers at minutes 2 and 3. At the start of minute 2, the balloon will be inflated to size 10, and will deflate to size 8 by the start of minute 3. At that point, the balloon\u0027s size will not change, but its deflation rate will change to 1. As a result, by the start of minute 6, its size will be 5.\u003c/p\u003e\r\n\u003cp\u003eNote that, if the offer at minute 1 is additionally taken, the balloon will simply be inflated to size 2 before deflating back to size 0 by the start of minute 2 - therefore, this will not change the outcome.\u003c/p\u003e\r\n\u003cp\u003eAlso note that, if the offer at minute 4 is additionally taken, the balloon will inflate to size 12 at the start of minute 4, but its deflation rate of 4 will result in a size of 4 at the start of minute 6, which is not optimal.\u003c/p\u003e\r\n\n\u003c/div\u003e"}}]}