Дарко е голем фудбалски фан, но тој е и голема мрза. За претстојното Светско Првенство во фудбал, тој сака да нарачува пиво од Интернет за достава до неговиот дом, за да не мора да стане од пред неговиот телевизор и така да ги изгледа сите натпревари на првенството.

Дарко веќе одбрал од кој сајт ќе ги прави нарачките, и сајтот нуди неколку видови на пиво. За секоја достава, сајтот наплаќа цена од D денари (без разлика на бројот на пива и колку видови на пиво се нарачуваат). Доставата се врши во истиот ден. Дополнително, за секој вид на пиво, позната ни е неговата цена, и колку денови пивото ќе биде вкусно (пред да се расипе од стоење). Дарко, според нутриционистичките препораки, ќе пие точно по едно пиво дневно, за да остане свеж за да ги изгледа сите натпревари кои се на програмата тој ден.

Доколку знаете дека Дарко има буџет од X денари, пресметајте колку најмногу денови може тој да пие безалкохолно пиво?

Влез

Во првиот ред се запишани два цели броја X и D, кои ги означуваат почетниот буџет (во денари) и цената за достава, (1 <= D <= X <= 1000000000). Во вториот ред е запишан бројот P (1 <= P <= 100), кој означува колку различни видови пива нуди сајтот за достава.

Во секој од следните P редови се запишани по два цели броја Ci (1 <= Ci <= X) и Vi (0 <= Vi <= 1000000000), кои означуваат дека цената за i-тиот вид на пиво е Ci денари, и истото е вкусно Vi дена од купувањето (на пример, доколку Vi=0 пивото мора да се испие истиот ден кога е купено, доколку Vi=1 мора да се испие тој ден или следниот, итн.).

Забелешка: Во тест случаи кои носат најмалку 50% од поените, X и Vi ќе бидат цели броеви помали или еднакви на 1000000.

Излез

Отпечатете го бараниот број на денови.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
31 6
2
8 1
5 0

излез
3

Објаснување за првиот пример: Првиот ден, Дарко може да купи едно пиво од првиот тип и едно пиво од вториот тип (за цена од 8+5+6=19 денари). Тој може да го испие пивото од вториот тип првиот ден, и она од првиот тип вториот ден. Третиот ден, Дарко може да нарача (и испие) уште едно пиво од вториот тип (за цена од 5+6=11 денари).