Tí được dịp nghỉ lễ đến tận ~N~ ngày. Trong ~N~ ngày này, Tí không muốn ra ngoài gặp bạn bè mà chỉ muốn làm tăng độ hạnh phúc của mình thông qua việc ăn bánh. Tí đã chuẩn bị sẵn ~M~ loại bánh. Biết rằng loại bánh thứ ~i~ sẽ hết hạn sau ngày thứ ~a_i~ của dịp nghỉ lễ, và độ hạnh phúc sau khi ăn loại bánh đó là ~b_i~. Tuy thích ăn bánh, nhưng Tí lại rất sợ béo nên chỉ có thể ăn tối đa ~1~ chiếc bánh trong ngày.

Yêu cầu: Bạn hãy giúp Tí thiết kế lộ trình ăn bánh trong ~N~ ngày để có thể đạt được độ hạnh phúc tối đa nhất có thể nhé.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên ~N~, ~M~ ~(2 \le N, M \le 10^5)~ lần lượt là số ngày nghỉ lễ và số loại bánh Tí đã chuẩn bị.
• ~M~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~a_i~, ~b_i~ ~(1 \le a_i \le N, 1 \le b_i \le 10^9)~ lần lượt là ngày cuối cùng có thể ăn được loại bánh ~i~ và độ hạnh phúc mà loại bánh này đem lại.

Dữ liệu ra

Một số nguyên duy nhất là độ hạnh phúc tối đa mà Tí có thể đạt được sau ~N~ ngày ăn bánh.

Giới hạn

• Subtask 1 (20% số điểm): ~2 \le N, M \le 20~
• Subtask 2 (80% số điểm): Không có giới hạn gì thêm.

Ví dụ

Dữ liệu vào

3 4
2 5
3 3
3 4
1 1

Dữ liệu ra

12