Mock CCO '18 Contest 3 Problem 5 - Roger Outsources DMOJ Work

View as PDF
Submit solution
Points: 15 (partial)
Time limit: 0.18s
Memory limit: 64M
Problem type

Roger has a lot of work to do for DMOJ, but he also needs to study for CCO!

Roger has decided to outsource some of his additional DMOJ work to Tudor. Tudor is unwilling to do the work for free though, so to boost his salary, he requests that Roger pay him for every task he is outsourcing. It takes Roger exactly one week to figure out all the tasks he wants to outsource to Tudor.

Roger's tasks have the interesting property that they must be completed in the order they are being outsourced to Tudor. Furthermore, each task will take Tudor exactly two weeks to do. In the first week, Tudor will do some preparation work, and he will charge Roger a reading fee for the preparation work. In the second week, Tudor will actually complete the task, and charge a resolving fee. Due to the nature of the work, for any given task, these two weeks must follow one immediately after the other, with no gap in between.

Roger must commit to paying these fees in a timely manner. Roger doesn't have very much money - every week, he can only afford to give Tudor at most M dollars. Roger's bank, to avoid fraud, will not permit Roger to withdraw more than M dollars, and because of how unsafe Canada is, Roger will withdraw the exact amount of money needed to pay Tudor in a week. Roger must pay Tudor for exactly the work he will do in a week, otherwise Tudor will refuse.

Roger needs the tasks completed as soon as possible. What is the minimum time until Tudor can finish all tasks?

Constraints

1 \le N \le 300

1 \le M \le 10^3

Input Specification

The first line will contain two integers, M and N.

Each of the next N lines will contain two integers, the reading fee and the resolving fee for each task. The tasks are presented in the order they must be completed.

Output Specification

Output a single integer, the minimum number of weeks needed for Tudor to do all of Roger's tasks.

Sample Input

100 5
40 20
60 20
30 50
30 50
40 40

Sample Output

6

Comments


  • 0
    Cueball1234  commented on July 17, 2018, 8:23 p.m.

    Sample Explanation

    Please correct me if I am wrong, but why isn't the sample output = 5?

    Week 1: 40, 60

    Week 2: 20, 20, 30, 30

    Week 3: 50, 50

    Week 4: 40

    Week 5: 40

    Thank you!


    • 1
      wleung_bvg  commented on July 17, 2018, 10:08 p.m.

      It takes Roger exactly one week to figure out all the tasks he wants to outsource to Tudor.


      • 0
        Cueball1234  commented on July 18, 2018, 5:02 a.m. ← edited

        Ah okay, so that one week is counted in the final answer as well. Thank you!