Little Z is studying university courses. It is known that Little Z needs to study $n$ courses and has a total time of $T$. All courses have a maximum ability level $k$. If Little Z's ability level in the $i$-th course is $a_i$ ($0 \le a_i \le k$), then he can obtain a profit of $v_{i, a_i}$. Little Z wants to maximize his total profit. Higher ability levels yield higher profits; specifically, it is guaranteed that $v_{i, j} \le v_{i, j+1}$ ($0 \le j < k$). He discovers that there are $m$ teachers in the university. Studying with the $i$-th teacher takes $t_i$ time, but can simultaneously help him improve his ability levels in $h_i$ courses. Let $l_{i, j}$ ($1 \le j \le h_i$) denote these courses. Specifically, when studying with the $i$-th teacher, if Little Z's ability level in the $l_{i, j}$-th course is less than $to_{i, j}$, his ability level in the $l_{i, j}$-th course will be increased to $to_{i, j}$. Now, for each $i$ such that $1 \le i \le T$, Little Z wants to find the maximum total profit from all courses given that the total time spent does not exceed $i$.

Input

The first line contains 4 space-separated integers, representing $n, m, k, T$ ($1 \le n \le 14, 1 \le m \le 50, 1 \le k \le 10^4, 1 \le T \le 50$). The next $n$ lines each contain $k+1$ integers, where the $(j+1)$-th integer ($0 \le j \le k$) represents $v_{i, j}$ ($0 \le v_{i, j} \le 10^9$). The next part contains information about the $m$ teachers. For each teacher, the first line contains 2 space-separated integers, representing $h_i, t_i$ ($1 \le h_i \le n, 1 \le t_i \le T$). The next $h_i$ lines each contain 2 space-separated integers, representing $l_{i, j}, to_{i, j}$ ($1 \le l_{i, j} \le n, 1 \le to_{i, j} \le k$).

Output

Output a total of $T$ lines, where the $i$-th line represents the maximum total profit when the total time spent does not exceed $i$.

Examples

Input 1

3 3 3 5
4 4 6 8
1 8 9 10
3 4 8 10
1 5
3 2
1 3
3 1
2 2
1 1
2 1

Output 1

8
15
15
15
16

Input 2

5 5 5 10
2 2 2 5 5 8
0 2 3 5 5 9
0 1 2 9 10 10
1 2 2 3 5 6
1 2 5 7 9 10
3 8
1 3
2 5
5 5
3 4
2 1
3 5
5 3
4 1
1 5
2 3
4 2
5 1
4 6
1 3
2 2
4 4
5 3
1 10
3 1

Output 2

17
17
17
22
32
32
32
32
32
32

Input 3

5 5 5 10
2 4 5 8 18 18
6 7 12 14 15 17
6 10 14 14 14 15
7 9 10 13 15 18
2 4 13 15 16 19
3 1
1 5
3 1
4 2
2 10
1 5
3 1
2 9
1 3
4 2
2 1

Output 3

60
76
76
76
76
76
76
76
76
76

Note

In the first example: When the study time does not exceed 1, without studying with any teacher, the ability levels for the three courses are $\{0, 0, 0\}$, and the profits are $\{4, 1, 3\}$ respectively. When the study time does not exceed 4, studying with the 3rd teacher, the ability levels for the three courses are $\{1, 1, 0\}$, and the profits are $\{4, 8, 3\}$ respectively. * When the study time does not exceed 5, studying with the 2nd and 3rd teachers, the ability levels for the three courses are $\{1, 1, 1\}$, and the profits are $\{4, 8, 4\}$ respectively.