U461935 MC_偷家
题目背景
**由于x变的日益强大，于是腐竹决定进行一波紫菜，去到他家，发现了许多物资，决定偷走一些**
题目描述
**腐竹发现了N个箱子，每个箱子有M格，每格对应着$A_i$个价值。求出偷走的最大价值（最多带走S个物品）**
输入格式
**第一行输入T，一共T组数据输入，接下来输入N，M，S接下来输入N行，每行M*M个物品**
输出格式
**求出其每组数据最大价值并且换行**
说明/提示
**$1 \le N \le 10, 1 \le M \le 1000, 1 \le A_i \le 100000000，1 \le S \le M，1\le T \le 10$**