oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

shoreline Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

shoreline.html

Problem Description

Rar the Cat is going to a holiday to Phuket! As Phuket is famous for its beautiful beaches, he decides to take a walk down one of them for fun.

Specifically, Rar the Cat is walking along a beach of length L metres, spanning a straight line from west to east, and he is travelling from the westernmost point to the easternmost point. There are N jetties located along the beach, where the ith jetty is located at Pi metres from the westernmost point, and has a length of Ai, stretching out into the ocean.

Rar is also an avid swimmer. Whenever he reaches the tip of a jetty, he can choose to jump down into the water and take a short swim, before coming back onto the same jetty.

While walking from west to east, Rar can, at any time, choose to walk down one of the jetties and take a short swim (or not). Specifically, he can choose a subset of these jetties to swim in. As Phuket's weather is very hot, he wants to pick this subset such that the maximum consecutive length he walks while out of water is minimised.

Refer to the sample explanation for more details.

Input

The first line of input will contain two integers, N and L.
The next N lines of input will contain two integers each, with the ith line containing integers Pi and Ai.

Output

Output a single line containing one integer, the minimum possible value of the maximum consecutive length of shoreline/jetty Rar the Cat walks out of water.

Limits

1 ≤ L ≤ 109, 1 ≤ Pi < L, 1 ≤ Ai ≤ 109

Subtask 1 (16%): 1 ≤ N ≤ 16.

Subtask 2 (21%): 1 ≤ N ≤ 2 000.

Subtask 3 (34%): 1 ≤ N ≤ 100 000.

Subtask 4 (29%): 1 ≤ N ≤ 1 000 000.

Subtask 5 (0%): Sample Testcases

Sample Testcase 1

Input

5 100
10 50
30 40
40 20
50 30
70 10

Output

60

Sample Testcase 2

Input

10 200
5 10
20 20
50 15
70 25
95 12
100 20
125 25
150 15
155 30
160 30

Output

67

Explanation for Sample 1

Rar the Cat will swim on jetties 3 and 5.

From the west point to jetty 3, Rar the Cat will travel 40 + 20 = 60 metres.

From the jetty 3 to jetty 5, Rar the Cat will travel 20 + (70 - 40) + 10 = 60 metres.

From jetty 5 to the east point, Rar the Cat will travel 10 + (100 - 70) = 40 metres.

Therefore, the maximum length Rar will spend out of water is 60 metres, and this is the minimum possible.

Tags

Greedy

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
116221s64MBMinimum
221421s64MBMinimum
334621s64MBMinimum
429821s64MBMinimum
5021s64MBMinimum

Judge Compile Command

g++-8 ans.cpp -o shoreline -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.