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 \leq T \leq 1000$, the number of rooms $R$ such that $1\leq R\leq 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.