T544238 「YAC Round 13」露易兹的旅行博客

 露易兹是魔界的知名旅行博主，这天她来到了一个名为“方格城”的城市，她想要在这座城市的旅行中增加尽可能多的人气值。

“方格城”地图可以抽象为一个 $n \times m$ 的矩阵，露易兹的起点在左上角 $(1, 1)$ 位置，每一步只能 **向右** 或 **向下** 移动一次（前提位置合法），最终到达右下角 $(n, m)$ 位置停止。 “方格城”中包含三种字符 `01?`。 露易兹在移动过程中，如果遇到字符 `0`，说明此处的居民对露易兹无感，可增加的人气值为 $0$；如果遇到字符 `1`，说明此处的居民很喜欢露易兹，可以增加 $1$ 人气值。 “方格城”中的 `?` 代表景点。露易兹非常喜欢拍照，当遇到字符 `?` 时，她可以在此景点拍照打卡并上传到自己的博客上，**同样可以增加 $1$ 人气值**。 但是，露易兹的相机容量是有限的，她 **最多只能拍 $p$ 次照**。 请你帮露易兹规划一下最优路线，求出露易兹 **最多可以增加多少人气值**。

**本题有多组测试数据** 第一行输入一个正整数 $T$（$1\le T \le 10$），代表测试用例组数。 对于每组测试数据： 第一行输入三个正整数 $n, m, p$（$1 \le n, m \le 500$，$1 \le p \le 300$），如题面所示。 接下来的 $n$ 行，每行一个长度为 $m$ 的仅含 `01?` 的字符串。 **数据保证 $\sum{n \times m} \le 2.5\times 10^5$**

对于每组测试用例： 输出一行一个整数，代表露易兹 **最多可以增加多少人气值**。

### 样例解释 对于第一组测试用例，最优路线为 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)$，在 $(3, 3)$ 处拍照，最终得分为 $5$。 对于第二组测试用例，最优路线可以是 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)$，可以在 $(2, 1)$ 或 $(2, 3)$ 处拍照，最终得分为 $2$。