Paint Rooms X63503

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 w_i and height h_i of a wall of the room r_i, and the money m_i Leonardo earns painting the i-th room.

Output

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