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

A certain pyramid has () rows, numbered from top to bottom. Each row has block spaces, which are labelled from left to right. Each block space in rows rests on top of two supporting block spaces in the row below it — block spaces and . For example, a pyramid with 6 rows is illustrated below, with block spaces , , and 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 ), 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 () different block spaces which must contain data - the of these is block space (). All of the other block spaces in the pyramid may either be filled with arbitrary 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 required block spaces contain data, and the entire data structure is stable.

#### Subtasks

- For 3 of the 15 marks available, and .
- For another 3 of the 15 marks available, and .
- For another 3 of the 15 marks available, and .

#### Input Specification

The first line of the input contains two integers, and . The remaining lines each contain two integers, and for .

#### Output Specification

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
```

#### Output for Sample Input

`15`

#### Explanation for Output for Sample Input

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.

## Comments

Is it guaranteed that the answer can be stored in a 64 bit integer? What if the test case is

`10e9 1 1 1`

?The answer to that case is on the order of , which fits in a 64-bit integer.

Sorry im dumb, i think i typed 2^54 into my calculator earlier

`10e9`

is actually ,`1e9`

is . That might be why.UGHH whats wrong with me, thx for all ur help

How is this a data structure problem?

You're right Data structure is not a data structure problem, Convex hull is not a convex hull problem, Gaussian elimination is not a Gaussian elimination problem, Heavy-light decomposition is not a heavy-light decomposition problem. This is the real world~

Raytracing is not a ray tracing problem, Gradient Descent is not a gradient descent problem.

Is anyone interested in making editorials for these ccoqr problems?