It's time for Oliver to do his daily chores. There are different types of chores. The type takes Oliver minutes to complete and there are chores of that type. Oliver starts a stopwatch and gets right to work on the chores. Each time he completes a chore, he writes down the time in minutes on the stopwatch, and then immediately starts completing his next chore. Once he has completed all the chores, he calculates his efficiency score by adding up all the times he wrote down. Can you help Oliver minimize his efficiency score?

#### Input Specification

The first line will contain one integer .

The next lines will each contain two integers. The line will contain and .

#### Output Specification

Print one integer, the minimum efficiency score possible. Since this number may be very large, output it modulo .

#### Sample Input 1

```
3
2 1
4 3
1 2
```

#### Sample Output 1

`43`

#### Sample Input 2

```
1
100 1000000000
```

#### Sample Output 2

`2100`

#### Sample Input 3

```
5
6 3
2 4
1 1
10 12
3 4
```

#### Sample Output 3

`1438`

## Comments