PEG Judge - NOI '06 - The Magical Bag

National Olympiad in Informatics, China, 2006

Day 2, Problem 3 - The Magical Bag

Pòlya received a magical bag with symbols written on it that are difficult for humans to understand. Pòlya is in awe of the symbols. As he is painstakingly trying to contemplate their meaning, he discovered a magical model (known to later generations as the Pòlya model). To make the teaching of his model more vivid and interesting, he created a game for his students to play.

At the start of the game, the bag contains a₁ balls of color 1, a₂ balls of color 2, …, a_t balls of color t, where a_i ∈ ℤ⁺ (1 ≤ i ≤ t).

After the game has started, the following actions are strictly followed at each step: Randomly draw a ball from the bag (there is equal probability for drawing any ball). After Pòlya individually looks at the color of the ball, he places the ball back into the bag, and then places d balls of this color into the bag.

Let c_i represent the color of the ball drawn during the i-th step (1 ≤ c_i ≤ t), then the process of the game will yield a color sequence (c₁, c₂, …, c_n, …).

Regarding the t types of colored balls at the start of the game, Pòlya has told all of the students the amount a₁, a₂, …, a_t of each type. Then he asks his students: What is the probability of the color sequence from a single game satisfying the following conditions?

c_x₁ = y₁, c_x₂ = y₂, …, c_{x_i} = y_i, …, c_{x_n} = y_n

where 0 < x₁ < x₂ < … < x_n and 1 ≤ y_i ≤ t. In other words, given (t, n, d, a₁, a₂, …, a_t, x₁, y₁, x₂, y₂, …, x_n, y_n), you must determine the probability of the following event: "for all k, 1 ≤ k ≤ n, the ball drawn in the x_k-th draw has color y_k."

Input Format

The first line contains three positive integer t, n (1 ≤ t, n ≤ 1000), and d (1 ≤ d ≤ 10).
The second line contains t integers a₁, a₂, …, a_t (1 ≤ a_k ≤ 10) representing the amount of each type of the t types of colored balls at the start of the game.
For the next n lines, each line contains a pair of positive integers x_i, y_i (1 ≤ x₁ < x₂ < … < x_n ≤ 10000; 1 ≤ y_k ≤ t), indicating that in step x_i, a ball of color y_i is drawn.

Output Format

Determine the answer in fraction form (it is clear that this probability is a rational number). Output a single line in the format: numerator/denominator. At the same time, output a reduced fraction (where the numerator and denominator are relatively prime). For the probability of 0, output 0/1. For the probability of 1, output 1/1.

Sample Input 1

Sample Output 1

1/12

Explanation of Sample 1

Initially, the amount of each of the two types of balls are (1, 1). The probability of drawing a ball with color 1 is 1/2.
Before the second draw, the amounts of the two types of balls are (2, 1). The probability of drawing a ball with color 2 is 1/3.
Before the third draw, the amounts of the two types of balls are (2, 2). The probability of drawing a ball with color 1 is 1/2.
Therefore, the total probability for all three draws is 1/12.