City Travel
Tag(s):

## Basic Programming, Basics of Implementation, Implementation, Very-Easy

Problem
Editorial
Analytics

You are going from City A to City B. The distance between A and B is $S$ km. In the most days, you can go at most $X$ km one day. But there are $N$ exceptions, in the $T_i$ th day, you can go at most $Y_i$ km. You need to find out the minimum number of days required to reach city $B$ from city $A$.

## Input Format

First line contains three integers, $S,X,N (1\le S,X\le 10^9,0\le N\le 10^3)$.

The $(i+1)$ th line contains two integers $T_i,Y_i(1\le T_i,Y_i\le 10^9)$.

It's guaranteed any two $T_i$ are different. Note that $T_i$ is not sorted.

## Output Format

SAMPLE INPUT
21 5 2
2 4
4 8

SAMPLE OUTPUT
4
Explanation

In the first day, you walked $5$km.

In the second day, you walked $4$km.

In the third day, you walked $5$km.

In the fourth day, you walked $7$km and arrived.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

September Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Sorting
• Math > Convex Hull
• Basic Programming > Recursion
• Algorithms > Dynamic Programming
• Data Structures > Trees