该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

快码公司的硬盘遇到了故障！工程师克利切洛夫斯基经过排查发现，故障的原因是他们的OJ把过多的数据存储在了硬盘上，读取量太大导致硬盘发生了损坏。

为了彻底解决这个问题，公司领导决定开发一个缓存系统。缓存系统可以将一部分访问较多的数据存储在内存而不是硬盘，来减少硬盘的压力。但内存的成本相比硬盘要高很多，所以他们需要你来帮忙开发一款高效的缓存系统，既能够满足存储在内存中的数据总大小不超过内存的容量，又能够尽可能多的减少硬盘的每日读取次数。

快码公司的OJ共有N道题目$\left(1<=N<=100\right)$，每道题目有M组不同的数据$\left(1<=M<=100\right)$。第i道题目的第j组数据占用的空间大小为$S_{ij}\left(1<=S_{ij}<=10,000\right)$，第j组数据每日需要进行的读取次数为$A_{ij}\left(1<=A_{ij}<=1,000,000,000\right)$。你可以选择一些数据放入内存中，这些数据就不需要再占用硬盘的读取次数，但要保证所有数据要么存储在硬盘中，要么在内存中。另一个要求是，如果要把某道题目的某一组数据存储在内存中，需要保证这道题目所有编号小于这组数据的其他数据都已经存储在了内存中。

现在请你求出，在内存总容量为X的情况下$\left(X<=5,000\right)$，硬盘每日读取次数最少是多少。

输入格式

本题有多组测试数据，第一行一个整数T表示测试数据的组数，$1\leq T \leq 10$。

对于每组测试数据，第一行三个整数N,M,X，分别表示题目的数量、每道题目的数据组数、内存的总容量。

接下来N×M行，每M行将描述一道题目的M组数据，其中每行包含两个整数，第$\left(i-1\right)×M+j$行的第一个整数表示第i道题目第j组数据占用的空间大小$S_{ij}$，第二个整数表示第i道题目第j组数据每日进行的读取次数$A_{ij}$。

保证所有测试数据中X的和不超过$10,000$。

输出格式

每组测试数据输出一行一个整数，表示在使用内存量不超过容量的最优策略下，硬盘每日读取次数最少是多少。

样例

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

15

限制

Time Limit: 2000ms Memory Limit: 524288KB