Fast Fingers Thomas is eating poutine at Wilson's restaurant. Thomas has dollars, and an order of poutine at Wilson's restaurant costs one dollar. Consequently, Thomas can place at most orders of poutine.

There are different types of poutine that Thomas can order. If Thomas orders poutine for the first time, he gains units of happiness. If Thomas orders poutine for the th time, he gains units of happiness. Wilson will never run out of any type of poutine.

Compute the maximum amount of happiness Thomas can feel after eating some amount of poutine.

#### Constraints

#### Input Specification

The first line of input contains two positive integers, and .

Each of the next lines contains two space-separated integers, and for poutine .

#### Output Specification

Let be the maximum attainable units of happiness that Thomas can feel. Output modulo .

#### Sample Input

```
2 3
8 2
7 2
```

#### Sample Output

`21`

## Comments