Frog’s River School Trips

A little frog lives by a river and wishes to attend school located on the opposite bank. The frog plans to cross the river by hopping on a line of stones. However, there is a twist: each stone has a \(\text{height}\) (its durability), and every time the frog jumps away from a stone (i.e. when it uses that stone as a stepping‐stone to jump to the next stone or bank), the stone’s height decreases by \(1\). A stone whose height reaches \(0\) cannot be used as a stepping stone any further (although it is allowed that a jump makes a stone’s height drop exactly to \(0\)).

The frog must attend school for x days. Since each day requires one round‐trip across the river, the frog must make a total of \(2x\) crossings. The frog has a jump ability \(y\): it can jump a distance of at most \(y\) in each hop. A valid hop must land either on a stone or directly on one of the banks. The banks are safe (they have no capacity restrictions).

Your task is to determine the minimum jump ability \(y\) the frog must have in order to complete \(2x\) trips using the available stones, without exceeding the capacity (height) of any stone. Note that if a jump from a stone causes its height to drop to 0, that jump is allowed, but the stone cannot be used thereafter.

Input and Output Details in brief:

• The river has width L (the distance between the two banks).
• There are n stones in the river. Each stone is described by its position (an integer in the open interval \((0,L)\)) and its height (a positive integer representing how many times it can be used as a departure stone).
• The frog’s jump ability \(y\) means it can only jump between two points (stones or banks) if the distance does not exceed \(y\).
• When the frog starts from a stone to make a jump, the stone’s height decreases by \(1\); bank jumps do not alter any capacity.
• The frog can directly jump from one bank to the other if the distance \(L\) is \(\le y\).

Goal: Compute the minimum \(y\) (an integer) such that there exists a plan for 2x trips (in both directions) that does not use any stone more times than its given height.

inputFormat

The first line contains three integers L, x, and n, where L is the width of the river, x is the number of days (so the frog makes \(2x\) trips), and n is the number of stones.

Then follow n lines, each containing two integers. Each line describes a stone: the first integer indicates the stone’s position (an integer, with \(0 < \text{position} < L\)) and the second integer indicates its height (its capacity, a positive integer).

You may assume that the stone positions are given in increasing order.

outputFormat

Output a single integer \(y\), the minimum jump ability required for the frog to complete all \(2x\) trips.

sample

10 2 4
2 2
4 2
7 2
8 2

4