Challenge 24 Electronic Contest Practice

Ten years have passed and some of the mistakes of the late mayor from Problem E have been slowly repaired. It turned out that with the constant noises from the tunnel digging machine the entertainment sector plummeted and people actually started doing their jobs instead of watching movies and playing games. You are one such born-again engineer and your task today is estimating the effectiveness of meteor defense systems installed above the tunnels. The meteor defense system consists of a shield that covers a number of segments of the tunnel and can be moved along the tunnel. Unfortunately the movement of this heavy instrument is really slow, as it can only be moved the distance of one segment per day. Astronomers have predicted the trajectories of incoming meteors for the next century. Your task is to calculate the maximum number of meteors that can be caught by the shield during this century.

Input:

The first line of the input consists of three integers, L, P and N, the number of segments of the tunnel, the number of tunnel segments the shield can cover and the number of the meteors in the century. The shield is always positioned in the first P segments of the tunnel (0, 1, . . . , P - 1) on the day 0. In the next N lines, the parameters of the meteors are given in chronological order. Each meteor is described by two integers T and S, where T is the day of the arrival (measured in the number of days elapsed since the installation of the shield) and S is the index of the segment where the meteor would hit the tunnel. (S is an integer from 0 to L-1.) Note that more than one meteor can arrive on the same day!

Output:

The output is a single integer, the total number of meteors that can be caught if the shield is moved optimally.

This is the text variant of the problem. Read more here about submitting solutions!

Example

Input:
10 3 4
0 3
5 5
6 0
7 0
Output:
2