Under the Umbrella#13062

Under the Umbrella

1 second

256 megabytes

Very hard

There are $n$ squirrels sitting on a line. The squirrel with number $i$ is located at the point with integer coordinate $x_{i}$ x_i, where $x_{1} < x_{2} < \dots < x_{n}$ x_1 < x_2 < \dots < x_n. The squirrels do not move.

You have an umbrella of length $w$ . If its left end is at point $p$ , then it protects all squirrels whose coordinates belong to the segment $[p, p + w]$ [p, p + w].

The umbrella must always be completely between the first and the last squirrel, that is, $x_{1} \leq p$ x_1 \leq p and $p + w \leq x_{n}$ p + w \leq x_n.

At time $0$ , you may freely choose any valid position of the umbrella. For each subsequent unit of time, you may move it one coordinate unit to the left, one coordinate unit to the right, or leave it in place.

There are $q$ nut falls. The $j$ -th fall is described by three integers $t_{j}$ t_j, $l_{j}$ l_j, and $r_{j}$ r_j: at time $t_{j}$ t_j, nuts fall on all squirrels whose coordinates belong to the segment $[l_{j}, r_{j}]$ [l_j, r_j].

If a squirrel is not under the umbrella during a fall, it gets injured. A squirrel is considered saved if it is not injured during any fall. Squirrels on which nuts never fall are also considered saved.

At each integer moment of time, first the movement of the umbrella during the previous unit of time finishes, and then all falls scheduled for that moment occur.

If several falls have the same time, they occur simultaneously, so the umbrella cannot be moved between them.

Find the maximum number of squirrels that can be saved.

Input

The first line contains three integers $n$ , $q$ , and $w$ ( $2 \leq n \leq 44$ 2 \leq n \leq 44, $1 \leq q \leq 2 \cdot 1 0^{5}$ 1 \leq q \leq 2 \cdot 10^5) — the number of squirrels, the number of nut falls, and the length of the umbrella.

The second line contains $n$ integers $x_{1}, x_{2}, \dots, x_{n}$ x_1, x_2, \dots, x_n ( $0 \leq x_{1} < x_{2} < \dots < x_{n} \leq 1 0^{9}$ 0 \leq x_1 < x_2 < \dots < x_n \leq 10^9) — the coordinates of the squirrels.

It is guaranteed that $1 \leq w \leq x_{n} - x_{1}$ 1 \leq w \leq x_n - x_1.

Each of the next $q$ lines contains three integers $t_{j}$ t_j, $l_{j}$ l_j, and $r_{j}$ r_j ( $1 \leq t_{j} \leq 1 0^{9}$ 1 \leq t_j \leq 10^9, $0 \leq l_{j} \leq r_{j} \leq 1 0^{9}$ 0 \leq l_j \leq r_j \leq 10^9) — the time of the fall and the boundaries of the segment on which nuts fall.

The falls are given in arbitrary order. Times of different falls may coincide.

Output

Print one integer — the maximum number of squirrels that can be saved.

Examples

Example 1

Example 2

Example 3

Note

In the first example, nuts fall on the squirrels at points $2$ , $4$ , and $7$ . An umbrella of length $3$ can protect at most two of them at the same time, for example the squirrels at points $2$ and $4$ . The squirrels at points $0$ and $10$ are not affected by any fall, so they are also saved. Therefore, the maximum number of saved squirrels is $4$ .

In the second example, all three falls happen simultaneously. Nuts fall on the squirrels at points $0$ , $4$ , and $8$ . An umbrella of length $1$ can protect only one of them. The squirrels at points $2$ and $6$ are not affected by any fall, so the maximum number of saved squirrels is $3$ .

In the third example, at time $1$ the umbrella can be positioned so as to protect the squirrel at point $0$ . By time $4$ , there is enough time to move the umbrella and protect the squirrel at point $5$ . Therefore, all $4$ squirrels can be saved.

Scoring

Subtask $1$ ( $30$ points): $q = 1$ q = 1.
Subtask $2$ ( $35$ points): all values $t_{j}$ t_j are equal.
Subtask $3$ ( $40$ points): $n \leq 10$ n \le 10, $q \leq 20$ q \le 20, $x_{n} \leq 20$ x_n \le 20, $t_{j} \leq 20$ t_j \le 20.
Subtask $4$ ( $50$ points): $n \leq 20$ n \le 20, $q \leq 2000$ q \le 2000.
Subtask $5$ ( $60$ points): $n \leq 20$ n \le 20.
Subtask $6$ ( $60$ points): $q \leq 2000$ q \le 2000.
Subtask $7$ ( $225$ points): No additional constraints.