### 问题描述

小 y 在玩一款矿工游戏，这个游戏界面可以简化成 $N \times M$ 的二维地图，地图中有 $K$ 个金块，每个金块有价值 $c_{i} \left( i \in \left[ 1, K \right] \right)$ 和花费时间 $t_{i}$ ，每个金块只能夹取一次。

小 y 可以从任意列的上方自由移动和向下夹取金块，如果金块 $i$ 所在列上方有未夹取的金块 $j \left( j \in \left[ 1, K \right] , j \neq i \right)$ ，小 y 需要先夹取金块 $j$ 才能夹取金块 $i$ 。

小 y 想知道她在 $T$ 时间内夹取金块获得的最大价值。

输入格式

第一行是四个整数 $N, M, T, K$，分别表示行数、列数、时间、金块数量。

接下来 $N$ 行，每行包含 $M$ 个整数，整数 $0$ 代表这格没有金块，正数 $i$ 表示这格的金块的编号。

接下来 $K$ 行，每行包含两个整数，分别表示花费时间 $t[i]$ 和金块价值 $c[i]$ 。

数据范围保证：$1 \leq N, M,K \leq 16$，$1 \leq t_{i} \leq T \leq 100$，$1 \leq c_{i} \leq 10^8$。

输出格式

输出共 $1$ 行，一个整数，小 y 在 $T$ 时间内夹取金块获得的最大价值。

样例输入

3 4 5 3
0 0 0 0 
0 1 3 0 
0 0 2 0 
1 1
4 5
1 4

样例输出

20

样例解释

夹取第 $2$ 个金块和第 $3$ 个金块可以获得最大价值。