Santa Claus

Interview

Time limit1sMemory limit1024 MB

Summary

Given N houses and depots with gift counts, find how many gifts to load at the start and at each depot so the sleigh holds as few as possible at all times.

Level: Medium5 of 10
Topics: Greedy, Array, Implementation
Solved: No attempts yet

Problem

Christmas is almost here. The reindeer are already harnessed, and Santa Claus is nearly ready to set off, but the gifts are not all loaded yet.

The sleigh can hold an unlimited number of gifts, but the reindeer team that pulls a heavy sleigh tires quickly. Gifts should therefore be loaded as few as possible.

Knowing this, the elves installed gift depots on the roofs of houses along Santa's route.

Santa Claus can load gifts at his own house (the starting point) and at any depot.

Given the number of children Santa must visit, find how many gifts he must load into the sleigh at his house and at each depot, so that the number of gifts in the sleigh is always as small as possible.

Santa travels as follows:

He visits the children in increasing order of house number, starting from the first house.
He cannot turn the sleigh back until he has visited all the children.
If a house has a depot on its roof, he first fills the sleigh with gifts from that depot, then delivers a gift to the child living in that house.

Every child lives in a different house, and each child receives exactly one gift.

Input

The first line contains two integers $N$ (the number of children) and $M$ (the number of gift depots). Each of the next $M$ lines contains two integers.

$K_i$ : the depot is on the roof of the house of the $K_i$ -th child. The values $K_i$ are given in increasing order.
$Z_i$ : the number of gifts in this depot.

Santa's house at the starting point has an unlimited number of gifts.

Output

Print $M + 1$ integers, each on its own line. The first line is the number of gifts Santa must load into the sleigh before starting the trip. The next $M$ lines are the number of gifts to load at each depot, in the same order as the depots appear in the input.

Constraints

$1 ≤ N ≤ 10\,000$
$0 ≤ M ≤ N$
$1 ≤ K_1 < \dots < K_i < K_{i+1} < \dots < K_M ≤ N$
$1 ≤ Z_i ≤ 10\,000$

Examples2

Example 1
Input
```
4 1
4 2
```
Expected output
```
3
1
```
Example 2
Input
```
5 2
2 1
5 100
```
Expected output
```
3
1
1
```