| The 2026 ICPC Belarus Qualification |
|---|
| Finished |
Svetozar started a channel on a popular video platform. His very first video was a huge success! On day $$$i$$$ it received $$$a_i$$$ likes, where $$$a_i$$$ is a nonnegative integer.
Unfortunately, after yet another redesign that buried the like counter behind six or seven menus, one has to press a great many buttons to obtain the full statistics, or even contact support!
Still, Svetozar does not need the full statistics yet. He has kept $$$n$$$ measurements showing that at the end of day $$$d_j$$$ the total number of likes was $$$s_j$$$ (for $$$j = 1, 2, \ldots, n$$$). Thus, $$$a_1 + a_2 + \ldots + a_{d_j} = s_j$$$.
Svetozar is interested in how many likes there could have been over $$$T$$$ consecutive days, considering only the first $$$d_n$$$ days. In other words, find the maximum theoretically possible sum $$$a_\ell + a_{\ell+1} + \ldots + a_{\ell+T-1}$$$ subject to $$$1 \leq \ell \leq d_n - T + 1$$$. Of course, a period of $$$T$$$ days need not start or end exactly on the days $$$d_1, d_2, \ldots, d_n$$$ for which the measurements are already available.
The first line contains integers $$$n$$$ and $$$T$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq T \leq 10^6$$$): the number of measurements and the length of the period.
The next $$$n$$$ lines contain integers $$$d_j$$$ and $$$s_j$$$: the measurement day and the total number of likes by the end of that day. It is guaranteed that $$$d_n \geq T$$$, that $$$1 \leq d_1 \lt d_2 \lt \ldots \lt d_n \leq 10^6$$$, and that $$$1 \leq s_1 \leq s_2 \leq \ldots \leq s_n \leq 10^9$$$.
Print an integer: the maximum possible number of likes over $$$T$$$ consecutive days.
3 22 44 96 12
9
In the sample, one possible sequence is $$$(0, 4, 5, 0, 3, 0)$$$. It is consistent with all measurements. On the second and third days, $$$4 + 5 = 9$$$ likes were received. No two consecutive days can yield more likes.
| Name |
|---|


