### 2016 Canadian Computing Olympiad Qualifying Round

## Problem Q3: Data Structure

It's a well-known fact that, inside computers, all data is stored in 2D pyramids of data blocks.

A certain pyramid has `N` (1 ≤ `N` ≤ 10^{9}) rows, numbered 1..`N` from top to bottom. Each row `r` has `r` block spaces, which are labelled (`r`, 1)..(`r`, `r`) from left to right. Each block space (`r`, `c`) in rows 1..(`N` − 1) rests on top of two supporting block spaces in the row below it – block spaces (`r` + 1, `c`) and (`r` + 1, `c` + 1). For example, a pyramid with 6 rows is illustrated below, with block spaces (3, 1), (4, 4), and (6, 2) indicated in red:

Now, each block space may either contain data, or be empty. A block space containing data is only stable if it's in the bottom row (row `N`), or if both of its two supporting block spaces also contain data. The entire pyramid is only stable if all of its non-empty block spaces are stable.

You know that there are `M` (1 ≤ `M` ≤ 10^{5}) different block spaces which must contain data – the `i`-th of these is block space (`r _{i}`,

`c`) (1 ≤

_{i}`c`≤

_{i}`r`≤

_{i}`N`). All of the other block spaces in the pyramid may either be filled with abitrary data or be left empty. However, everyone knows that data is expensive. As such, you're interested in the smallest amount of data that the pyramid's block spaces can contain such that at least the

`M`required block spaces contain data, and the entire data structure is stable.

### Subtasks

For 3 of the 15 marks available, `N` ≤ 100 and `M` ≤ 200.

For another 3 of the 15 marks available, `N` ≤ 2000 and `M` ≤ 10^{5}.

For another 3 of the 15 marks available, `N` ≤ 10^{9} and `M` ≤ 2.

### Input Format

The first line of the input contains two integers, `N` and `M`. The remaining `M` lines each contain two integers, `r _{i}` and

`c`for

_{i}`i`= 1..

`M`.

### Output Format

Output a single integer, the minimum number of block spaces which can contain data such that the entire pyramid is stable. Note that this value may not fit in a 32-bit signed integer, and may need to be stored in a `long long`

/ `long`

/ `int64`

variable in C++ / Java / Pascal, respectively.

### Sample Input

6 3 3 1 4 4 6 2

### Sample Output

15

### Explanation

The diagram below illustrates the pyramid described by the sample case, where the 3 red block spaces must contain data, while the 12 orange block spaces represent the optimal set of blocks to additionally fill with data to make the entire pyramid stable.

All Submissions

Best Solutions

**Point Value:** 17 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 256M

**Added:** Mar 09, 2016

**Author:** SourSpinach

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

ImaxBlueon Mar 12, 2016 - 12:02:52 am UTC Test case 4:adjargonon Mar 12, 2016 - 11:19:42 pm UTC Re: Test case 4:adEdit: I've rejudged at least one submission for each user to whom this would make a difference.