Paint Rooms X63503


Statement
 

pdf   zip

html

Leonardo was walking in Rome, where a lot of emblematic buildings were not maintained at all, so he decided to start a new business for tourism promotion, earning as much money as possible within a limited time window.

How many rooms can Leonardo paint in a workday? Luca Pacioli, a good old friend of Leonardo, helped him to extract the formula of the required time, where Luca said: "You are a really fast painter, so you just need 1 minute per square meter".

Given the time Leonardo has to paint the rooms, the width and height of a wall and taking into account each room has 4 similar walls and the roof, and the money Leonardo can earn for each room, print the maximum amount of money Leonardo can earn.

Input

The input consists of several test cases. Each test case consists of a total time T where 50 ≤ T ≤ 1000, the number of rooms R such that 1≤ R≤ 1000, and the next R lines have the width wi and height hi of a wall of the room ri, and the money mi Leonardo earns painting the i-th room.

Output

For each test case, return the maximum amount of money Leonardo can earn painting rooms.

Public test cases

  • Input

    80 3
2 5 17
1 2 15
3 2 16

96 4
4 1 10
4 1 10
4 1 10
4 5 31

96 4
4 1 11
4 1 11
4 1 11
4 5 31

    Output

    33
31
33
    • Information
    Author
    Javier Segovia
    Language
    English
    Official solutions
    Unknown. This problem is being checked.
    User solutions
    C++