小 Ellie 有两个应用程序需要尽可能快地执行。应用程序 $i$ ($i=1,2$) 由 $ns(i)$ 个相同的步骤组成，编号为 $1$ 到 $ns(i)$。Ellie 拥有一个由 $M$ 台机器（编号为 $1$ 到 $M$）组成的集群，她可以在这些机器上执行这两个应用程序的步骤。这些机器并不完全相同，这意味着在每台机器上执行一个步骤的持续时间可能不同。更具体地说，在机器 $j$ 上执行应用程序 $i$ 的一个步骤需要 $T(i,j)$秒。

由于每个应用程序的步骤都是高度 CPU 密集型的，因此一台机器在同一时间只能执行一个应用程序的一个步骤（即，如果两个应用程序的多个步骤被安排在同一台机器上执行，则它们执行的时间区间必须不相交，或者仅在端点处相交）。此外，任何应用程序的任何步骤在任何机器上的执行都不能被暂停并在以后重新开始（无论是在同一台机器上还是在另一台机器上）。这意味着，一旦某个步骤在某台机器上开始执行，Ellie 要么让其成功执行完毕，要么在执行完毕前的任何时间取消它，并在稍后从头开始重新执行（在同一台机器或任何其他机器上）。

由于数据依赖性，同一应用程序 of 的步骤必须顺序执行（即，应用程序 $i$ 的步骤 $j$ 只能在同一应用程序的步骤 $j-1$ 执行完毕后才能开始——可以恰好在步骤 $j-1$ 结束的时刻，也可以在之后的任何时刻）。步骤 $j$ 的执行既可以安排在执行步骤 $j-1$ 的同一台机器上，也可以安排在任何其他机器上。不同应用程序的两个步骤之间没有依赖关系。

假设 Ellie 可以在时刻 $0$ 开始执行这两个应用程序的步骤，她希望最小化任何应用程序的最后一个步骤完成执行的时刻 $T_{END}$（以秒为单位）。请告诉她 $T_{END}$ 的最小可能值以帮助她。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例的描述。

每个测试用例由 3 行组成：

• 第一行包含三个整数：$ns(1)$，$ns(2)$ 和 $M$。
• 第二行包含 $M$ 个整数，依次表示：$T(1,1), T(1,2), \dots, T(1,M)$。
• 第三行包含 $M$ 个整数，依次表示：$T(2,1), T(2,2), \dots, T(2,M)$。

输出格式

对于每个测试用例（按照输入中给出的顺序），在单独的一行中输出 $T_{END}$ 的最小可能值。

数据范围

• $1 \le T \le 20$
• $1 \le ns(i) \le 1000000$ ($10^6$)
• $1 \le M \le 10$
• $1 \le T(i,j) \le 1000$

样例

输入格式 1

6
1000000 1000000 1
1
2
999999 999998 5
1 2 3 4 5
5 4 3 2 1
765432 765 2
1 2
1 1000
765432 766 2
1 2
1 1000
3 5 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
10 10 5
101 102 103 104 105
101 102 104 105 103

输出格式 1

3000000
999999
765432
765433
6
1016

说明

样例 1：由于只有一台机器，两个应用程序的所有步骤都在这唯一可用的机器上执行。所有步骤执行完毕所需的时间为 $1000000 \times 1 + 1000000 \times 2 = 3000000$。

样例 2：应用程序 1 的所有步骤都在机器 1 上执行，应用程序 2 的所有步骤都在机器 5 上执行。所有步骤完成所需的时间为 $\max(999999 \times 1, 999998 \times 1) = 999999$。

样例 3：应用程序 1 的所有步骤都在机器 1 上执行，应用程序 2 的所有步骤都在机器 2 上执行。所有步骤完成所需的时间为 $\max(765432 \times 1, 765 \times 1000) = 765432$。

样例 4：应用程序 1 的所有步骤都在机器 1 上执行，应用程序 2 的前 765 个步骤在机器 2 上执行。在应用程序 2 的前 765 个步骤于时刻 765000 执行完毕后，Ellie 等待到时刻 765432（此时机器 1 变得可用）。然后她将应用程序 2 的最后一个步骤安排在机器 1 上，其执行在时刻 765433 结束。

样例 5：应用程序 1 的所有步骤都在机器 2 上执行，应用程序 2 的所有步骤都在机器 1 上执行。所有步骤完成所需的时间为 $\max(3 \times 2, 5 \times 1) = 6$。