G. Great Tourist
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ana, a great tourist, decided to take advantage of the border between Foz do Iguaçu and Ciudad Del Este and go shopping in Paraguay. She has a list of $$$N$$$ products she would like to bring back. However, when crossing the Friendship Bridge, there is a risk of being stopped by the Federal Revenue Service. To minimize this risk, Ana imposes two restrictions on what she will bring with her:

  1. The sum of the prices of the products cannot exceed $$$K$$$;
  2. Some pairs of products $$$\{i, j\}$$$ have a higher risk of being stopped if they are taken together. Ana does not want to take any chances, so she will take at most one product from each of these pairs.
Input

The first line of the input contains three integers: $$$N$$$ ($$$2 \leq N \leq 20$$$), $$$M$$$ ($$$0 \leq M \leq N(N-1)/2$$$), and $$$K$$$ ($$$1 \leq K \leq 10^{18}$$$), the number of products, the number of forbidden pairs, and the maximum limit.

The second line of input contains $$$N$$$ numbers $$$a_1, a_2, ..., a_N$$$, the price of the $$$i$$$-th product ($$$1 \leq a_i \leq 10^{18}$$$).

The next $$$M$$$ lines are distinct and each contain a pair of numbers $$$i$$$ and $$$j$$$ ($$$1 \leq i \lt j \leq N)$$$, representing the indices of the products that have a higher risk of being stopped if taken together.

Output

Output the number of product subsets that Ana can choose from that meet the constraints.

Examples
Input
4 1 100
1 2 3 4
1 2
Output
12
Input
4 1 8
1 2 3 4
1 2
Output
11