题目描述

这是一个很奇怪的游戏。

你是一名勇者，拥有 \(n\) 项属性（标号从 1 到 \(n\)）。挑战 Boss 时，你对 Boss 造成的伤害由每项属性值决定，因为一些奇怪的特性，并不是你的属性越高你对 Boss 的伤害就越高，具体而言：

对于第 \(i\) 项属性，给定两个参数 \(l_i\) 和 \(r_i\)，设你的第 \(i\) 项属性值为 \(a_i\)，则该属性对 Boss 造成的伤害 \(p_i\) 满足：

\[ p_i = \begin{cases} 0, & a_i < l_i \lor a_i > r_i \\ f_{i, a_i-l_i}, & l_i \le a_i \le r_i \end{cases} \]

你最终对 Boss 造成的总伤害为所有属性伤害之和： \(\sum_{i = 1}^{n}p_i\)。

初始时，你的所有属性值均为 0。你有 \(m\) 个属性加成可选，每种加成最多选择一次，第 \(i\) 个加成会使你的第 \(j\) 项属性增加 \(g_{i, j}\)。请计算你能造成的伤害的最大值。

输入格式

第一行输入一个正整数 \(t\)，表示数据组数。

对于每组数据：

• 第一行输入三个正整数 \(n, m, k\) （\(n\) 为属性种类数， \(m\) 为加成选择数， \(k\) 满足 \(\sum_{i = 1}^{m} \sum_{j = 1}^{n}g_{i, j} = k\)）。
• 第 2 行到第 \(n+1\) 行：第 \(i+1\) 行先输入 2 个正整数 \(l_i\) 和 \(r_i\)，随后输入 \(r_i-l_i+1\) 个正整数 \(f_{i, 0}, f_{i, 1}, \dots, f_{i, r_i-l_i}\)。
• 第 \(n+2\) 行到第 \(n+m+1\) 行：第 \(n+1+i\) 输入 \(n\) 个非负整数 \(g_{i, 1}, g_{i, 2}, \dots, g_{i, n}\)。

对于所有数据满足：

• \(t \le 10\)
• \(n \le 6\)
• \(m \le 30\)
• \(k \le 150\)
• \(40 \le l_i \le r_i \le 150\)
• \(1 \le f_{i, j} \le 10000\)
• \(0 \le g_{i, j} \le k\)

输出格式

对于每组数据，输出一行一个整数，表示能造成的伤害的最大值。

样例输入

2
3 5 130
40 50 7 6 3 8 9 6 7 3 3 3 7
40 50 1 1 5 2 10 8 8 9 1 10 2
40 50 1 6 4 8 10 10 7 1 10 3 2
9 7 7
13 9 9
13 9 4
7 8 13
7 4 11
3 5 130
40 50 2 1 4 1 2 8 9 6 8 2 5
40 50 2 10 10 10 4 10 7 8 4 9 9
40 50 4 1 7 6 9 10 8 10 4 3 9
15 9 6
4 11 10
8 8 8
9 12 4
9 9 8

样例输出

13
17