U28551.进攻皇宫

普及+/提高

NOI Online

通过率:0%

时间限制:3.00s ~ 3.00s

内存限制:128MB

题目描述

起义军不满皇帝的暴力制度,发起了起义,起义军势如破竹,很快就打到了皇宫脚下。起义军看到皇帝的皇宫的奢华,十分愤怒,决定一把火烧了皇宫。
已知起义军可以用3个火把,每个火把可以点燃以自身为中点33×\times33的范围,皇宫大小为nn×\timesmm。起义军的目标是尽可能烧掉更多奢侈品。为了更好达成目标,起义军已经在皇宫平面图上进行了标记:dollar符为奢侈品,“*”为空地。起义军已经统计好了奢侈品数量为tt。请你帮起义军找到尽可能烧掉更多奢侈品的方法。

输入格式

第一行输入nnmmttLL(1<=n,m<=10000,0<=t,L<=n*m)
接下来输入一个nn×\timesmm的矩阵,其中有tt个dollar

输出格式

一行,输出最多能烧掉多少奢侈品(dollar)

输入输出样例

  • 输入#1

    5 9 11
    ****$**$*
    $$$******
    *******$*
    $$$******
    ****$**$*

    输出#1

    9

说明/提示

火把可以放在奢侈品上

首页