Lights of Apartment

Problem

A-chan, Rika-chan, and Hart-kun came to visit the condominium. The three decided to sneak into a room where they could manage the electricity in all the rooms and play a trick.

This condominium has the shape of n cubes lined up in a row. Each cube has one side length increasing by 1 from the west (1,2,3, ..., n), the i-th cube has i floors, and each floor has i x horizontal rooms. There is. The west side of the second and subsequent cubes borders the east side of one west cube, and the south side of all cubes faces a straight road.

At first, all rooms have electricity. Each of the three took the following actions.

• A-chan turned off the lights in all the kth rooms from the west.
• Licca turned off the lights in all the kth rooms from the south.
• Hart turned off the lights in all rooms on the k floor.

Find the number of rooms that are lit after such mischief has been done m times.

Constraints

• 1 ≤ n, m ≤ 50000
• 0 ≤ qi ≤ 2
• 1 ≤ ki ≤ 2 × 109
• The same action can only be given once

Input

n m q1 k1 ... qm km

All inputs are given as integers. The number n of cubes and the number m of actions are given in the first line. The numbers q and k of the person who acted on the second and subsequent lines m are given.

When qi is 0, it means that A-chan, when it is 1, it means that Rika-chan, and when it is 2, it means that Hart-kun has acted.

The three may try to turn off the lights in places where there is no room.

Output

Output the number of rooms with electricity in one line.

Examples

Input

3 1 0 4

Output

27

Input

3 2 2 2 2 3

Output

14

inputFormat

Input

n m q1 k1 ... qm km

All inputs are given as integers. The number n of cubes and the number m of actions are given in the first line. The numbers q and k of the person who acted on the second and subsequent lines m are given.

When qi is 0, it means that A-chan, when it is 1, it means that Rika-chan, and when it is 2, it means that Hart-kun has acted.

The three may try to turn off the lights in places where there is no room.

outputFormat

Output

Output the number of rooms with electricity in one line.

Examples

Input

3 1 0 4

Output

27

Input

3 2 2 2 2 3

Output

14

样例

3 2
2 2
2 3

14