hackercupai/hackercup huggingface dataset:
You know what a finshake is, right? It's just like a handshake. Except
performed by fish rather than humans.

There are **N** pools of water in a row, numbered from 1 to **N** in order.
Pool _i_'s water level is at an elevation of **Hi** metres. There are **N** \-
1 equally-tall walls, one between each pair of adjacent pools, with the top of
each wall at an elevation of **W** metres. All of the water levels are lower
than the tops of the walls (in other words, **Hi** < **W** for each _i_).

There are also **M** fish throughout the pools. The _i_th fish initially lives
in pool **Pi**, and has a jumping height of **Ji** metres. It can jump over a
wall from any given pool **a** to an adjacent pool **b** (such that |**a** \-
**b**| = 1) if and only if **Ji** > **W** \- **Ha**. Multiple fish may live in
the same pool.

Each of the **M** fish will spend some time jumping over walls amongst the
pools, before each choosing a final pool to settle in. After all of the fish
have settled down, for each unique unordered pair of fish who have ended up in
the same pool as one another, they will give each other a finshake. Assuming
the fish all work together, what's the maximum number of finshakes which can
occur once they've all settled down in their chosen pools?

### Input

Input begins with an integer **T**, the number of rows of pools. For each row
of pools, there is first a line containing the space-separated integers **N**,
**M**, and **W**. Then follows a line containing the **N** space-separated
integers **H1** through **HN**. Then **M** lines follow, the _i_th of which
contains the space-separated integers **Pi** and **Ji**.

### Output

For the _i_th row of pools, output a line containing "Case #_i_: " followed by
the maximum number of finshakes which can occur.

### Constraints

1 ≤ **T** ≤ 50
1 ≤ **N** ≤ 500
1 ≤ **M** ≤ 50
2 ≤ **W** ≤ 1,000,000
1 ≤ **Hi** < **W**
1 ≤ **Pi** ≤ **N**
1 ≤ **Ji** ≤ 1,000,000

### Explanation of Sample

In the first case, neither fish has a sufficient jumping height to jump over
the wall from its own pool to the other pool. As such, each fish must remain
isolated in its own pool, resulting in 0 finshakes being exchanged.

In the second case, the second fish has sufficient jumping strength to go back
and forth over the wall. It should choose to settle in the first pool. With
both fish ending up in the same pool, they'll exchange 1 finshake.

In the third case, the first fish is unable to leave the first pool. The
fourth fish could decide to choose to stay in the first pool as well, and give
the first fish a finshake. However, it's better for the last 3 fish to all
congregate in the second pool instead, as this will result in a total of 3
finshakes being exchanged amongst them.