Galactic Container Ship

Interview

Time limit1sMemory limit128 MB

Summary

Given M rails with height limits 1..M and N plates each worth its quality w and having height h, choose plates to maximize total quality so that each chosen plate fits some distinct rail.

Level: Medium5 of 10
Topics: Greedy, Sorting, Heap
Solved: No attempts yet

Problem

A clay mine on Mars digs up red carbon-silicon clay and presses it into plates that are easy to transport. Every plate has the same standard width and thickness, but plates can differ in height and in material quality. There are 1000 quality classes, and plates are produced in heights of 1, 2, ..., 500000mm. The price of a plate depends only on its material quality, not on its height: a plate made of class $q$ material costs $q$ galactars.

A galactic container ship carries these plates. Its cargo hold is a hall with $M$ rails mounted in parallel in the floor; each rail can hold exactly one plate. The hold has a slanted ceiling: at one end it is $1$ mm high and at the other end it is $M$ mm high. That is, the ceiling above the rail numbered $n$ is exactly $n$ mm high, so that rail can hold only a plate whose height is at most $n$ .

A pile of plates waiting to be shipped sits at the dock. The captain wants to load cargo of the greatest possible total value, but is limited by the size of the hold (the plates cannot be trimmed). The experienced crew always chooses the load optimally, following the captain's wishes. Determine how much the captain must pay for the optimal load.

Write a program that:

reads the size of the hold and the sizes of the plates on the pile,
computes the maximum total value of cargo that can be loaded,
prints that maximum value.

Input

The first line contains two natural numbers $M$ and $N$ separated by a space ( $1 \le M \le 500000$ , $0 \le N \le 1000000$ ). $M$ is the length and the maximum height of the hold, and at the same time the number of rails; $N$ is the number of plates on the pile. Each of the next $N$ lines describes one plate as two natural numbers $w$ and $h$ separated by a space ( $1 \le w \le 1000$ , $1 \le h \le 500000$ ): $w$ is the quality class of the plate's material and $h$ is the plate's height in millimeters. Note that the pile may contain plates taller than the maximum height allowed in the hold.

Output

Print a single integer: the value of the optimal load.

Examples3

Example 1
Input
```
10 5
2 1
3 2
5 2
2 10
3 10
```
Expected output
```
13
```
Example 2
Input
```
5 0
```
Expected output
```
0
```
Example 3
Input
```
4 4
5 1
5 2
5 3
5 4
```
Expected output
```
20
```