### 问题描述 小 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$ 时间内夹取金块获得的最大价值。 ### 样例输入 ```plaintext 3 4 5 3 0 0 0 0 0 1 3 0 0 0 2 0 1 1 4 5 1 4 ``` ### 样例输出 ```plaintext 20 ``` ### 样例解释 夹取第 $2$ 个金块和第 $3$ 个金块可以获得最大价值。