Pòlya obtained a wonderful bag with symbols on it that are difficult for humans to understand. Fascinated and deep in thought, Pòlya discovered a magical model (later known as the Pòlya Urn model). To vividly teach this magical model, he and his students played a virtual game:

At the beginning of the game, the bag contains $a_1$ balls of color 1, $a_2$ balls of color 2, ..., $a_t$ balls of color $t$, where $a_i \in \mathbb{Z}^+$ ($1 \le i \le t$).

After the game starts, the following operation is strictly performed each time: A ball is randomly drawn from the bag (all balls in the bag have an equal probability of being drawn). Pòlya observes the color of the ball, puts it back, and then adds $d$ balls of the same color into the bag.

Let $c_i$ denote the color of the ball drawn in the $i$-th operation ($1 \le c_i \le t$). A game process will produce a color sequence $(c_1, c_2, \dots, c_n, \dots)$.

Pòlya told all the students the number of balls of each of the $t$ colors at the start of the game: $a_1, a_2, \dots, a_t$. Then he asked the students: What is the probability that the color sequence produced in one game process satisfies the following conditions?

$$c_{x_1} = y_1, c_{x_2} = y_2, \dots, c_{x_n} = y_n$$

where $0 < x_1 < x_2 < \dots < x_n$ and $1 \le y_i \le t$. In other words, given $(t, n, d, a_1, a_2, \dots, a_t, x_1, y_1, x_2, y_2, \dots, x_n, y_n)$, you need to answer the probability that the following event occurs: "For all $k, 1 \le k \le n$, the color of the ball drawn at the $x_k$-th time is $y_k$."

Input

The first line contains three positive integers $t, n, d$. The second line contains $t$ positive integers $a_1, a_2, \dots, a_t$, representing the number of balls of each of the $t$ colors in the bag at the start of the game. The following $n$ lines each contain two positive integers $x_i, y_i$, representing that the ball drawn at the $x_i$-th time is of color $y_i$.

Output

The probability must be output in the form of a fraction (it is clear that this probability is a rational number). The output file contains one line in the format: Numerator/Denominator. The output must be in simplest form (the numerator and denominator must be coprime). Specifically, a probability of 0 should be output as 0/1, and a probability of 1 should be output as 1/1.

Examples

Input 1

2 3 1
1 1
1 1
2 2
3 1

Output 1

1/12

Input 2

3 1 2
1 1 1
5 1

Output 2

1/3

Note

Explanation for Example 1: Initially, the number of balls of the two colors is $(1, 1)$, and the probability of drawing a ball of color 1 is $1/2$. Before the second draw, the number of balls of the two colors is $(2, 1)$, and the probability of drawing a ball of color 2 is $1/3$. Before the third draw, the number of balls of the two colors is $(2, 2)$, and the probability of drawing a ball of color 1 is $1/2$. Therefore, the total probability of the three draws is $1/12$.

Constraints

$1 \le t, n \le 1000$ $1 \le a_k, d \le 10$ $1 \le x_1 < x_2 < \dots < x_n \le 10000$ $1 \le y_k \le t$

Subtasks

This problem has no partial points. Your program's output must be exactly consistent with our answer to receive full marks; otherwise, no points will be awarded.