描述
百度noip贴吧管理组开发了一个小游戏，叫魔塔魔塔。虽然把魔塔重复了两次，但其实还只是个魔塔而已，还是简化版的。游戏在一个N*M大小的地图中进行，每一格都是正方形。
对于某一格，有若干种可能的状态：
1）空格，用“.”表示。人畜无害。
2）陷阱，用“D”表示。踩一次会掉一些血，踩R次就会死亡。
3）墙，用“#”表示。不能踩上这样的格子。
4）宝物，用P表示。表示格子里有宝物，每个宝物都有一定的价值。同时宝物需要一些钥匙去开启，有三种不同的钥匙：红色、蓝色、绿色，每一个宝箱都需要最多三把钥匙打开。
5）出生点，用“S”表示。
对于某一格，有若干种可能的状态：
1）空格，用“.”表示。人畜无害。
2）陷阱，用“D”表示。踩一次会掉一些血，踩R次就会死亡。
3）墙，用“#”表示。不能踩上这样的格子。
4）宝物，用P表示。表示格子里有宝物，每个宝物都有一定的价值。同时宝物需要一些钥匙去开启，有三种不同的钥匙：红色、蓝色、绿色，每一个宝箱都需要最多三把钥匙打开。
5）出生点，用“S”表示。
现在你扮演着游戏中的勇者，正准备出发去购买宝物。一开始你有一些钱Q，你可以用这些钱向神秘商人Nettle购买一些红色、蓝色、绿色钥匙，价格分别是R，B，G。当你购买了钥匙后，就可以进入地图探险了，与此同时神秘商人Nettle就会离开，也就是说一旦进入地图，你就不能再购买钥匙了。一开始你在出生点，其中当你身上没有宝物时，你可以以1秒的时间从某个向上、下、左、右四个方向移动一格。当你遇到一个宝物，你可以选择拾起或不拾起（不浪费时间），但是一旦拾起就必须将其搬回游戏出生点，并且每步需要耗费3秒的时间。
这个游戏有时间限制K秒。请你计算出在K秒内能获得的最大价钱。注意你一开始的金钱没有使用的部分也计算在内。
输入格式
输入第一行是五个数N，M，K，Q，R，表示地图的大小、时间限制、金钱数量和陷阱最多能踩的次数。（1<=N,M<=20，0<=K<=800，0<=Q<=100，0<=R<=10）
之后是一个N*M的字符矩阵，表示地图上面的物品数量。
之后是一行三个数R，B，G，表示红色、蓝色、绿色钥匙的价格。（1<=R,B,G<=100）
之后是若干行（直至文件末尾EOF，你可以使用while(scanf()!=EOF)或者while not seekeof(input)读入），每行有六个数X，Y，A，B，C，V，表示在(x,y)处的宝箱需要A把红色钥匙B把蓝色钥匙C把绿色钥匙打开，价格为V。（0<=V<=5000，0<=A+B+C<=3）
保证读入合法，并且只有一个S。
之后是一个N*M的字符矩阵，表示地图上面的物品数量。
之后是一行三个数R，B，G，表示红色、蓝色、绿色钥匙的价格。（1<=R,B,G<=100）
之后是若干行（直至文件末尾EOF，你可以使用while(scanf()!=EOF)或者while not seekeof(input)读入），每行有六个数X，Y，A，B，C，V，表示在(x,y)处的宝箱需要A把红色钥匙B把蓝色钥匙C把绿色钥匙打开，价格为V。（0<=V<=5000，0<=A+B+C<=3）
保证读入合法，并且只有一个S。
输出格式
输出只有一行，表示最多能获得的宝物价格。
测试样例1
输入
5 5 10 100 1
#####
#P#P#
#.#D#
#...#
##S##
50 50 1
2 2 1 1 1 100
2 4 0 0 0 5000
输出
100
/*
bfs预处理，加一个背包dp,处理比较暴力，90分
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#define fo(i,l,r) for(int i = l;i <= r;i++)
#define fd(i,l,r) for(int i = r;i >= l;i--)
using namespace std;
struct dat{
int y;
int x;
int bl;
int stp;
};
struct ITM{
int x;
int y;
int r;
int b;
int g;
int v;
}itm[];
int ans;
int n,m,k,q,r,p_r,p_b,p_g;
int am_p,am_t,sx,sy;
int d[][][];
int dp[][][];
int dx[] = {,,-,};
int dy[] = {,-,,};
vector<int> mb[][];
bool vis[][][];
char mp[][];
inline bool judge(int y,int x){
if(y > n||y < ||x > m||x < ||mp[y][x]=='#') return false;
else return true;
}
inline int get_p(int t_r,int t_b,int t_g){
return t_r*p_r + t_b*p_b + t_g*p_g;
}
int read(){
int x=,f=;
char ch=getchar();
while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};
while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};
return x*f;
}
void input(){
n = read();
m = read();
k = read();
q = read();
r = read();
for(int i = ;i <= n;i++) scanf("%s",mp[i]+);
fo(i,,n){
fo(j,,m){
if(mp[i][j] == 'S') sy = i,sx = j;
}
}
p_r = read();
p_b = read();
p_g = read();
int X,Y,A,B,C,V;
while(scanf("%d%d%d%d%d%d",&X,&Y,&A,&B,&C,&V)!=EOF){
am_p++;
itm[am_p].y = X;
itm[am_p].x = Y;
itm[am_p].r = A;
itm[am_p].b = B;
itm[am_p].g = C;
itm[am_p].v = V;
}
}
void bfs(){
dat now,to;
queue<dat> q;
now.y = sy;
now.x = sx;
now.bl = ;
now.stp = ;
q.push(now);
vis[now.y][now.x][now.bl] = true;
while(!q.empty()){
now = q.front();
q.pop();
fo(k,,){
to.y = now.y + dy[k];
to.x = now.x + dx[k];
if(!judge(to.y,to.x)) continue;
to.bl = now.bl;
to.stp = now.stp+;
if(mp[to.y][to.x] == 'D') to.bl++;
if(to.bl > r) continue;
if(!vis[to.y][to.x][to.bl]){
vis[to.y][to.x][to.bl] = true;
d[to.y][to.x][to.bl] = to.stp;
mb[to.y][to.x].push_back(to.bl);
q.push(to);
}
}
}
}
void get_ans(){
int ny,nx,np,cta,ctb,ctm,get_m;
fo(bx,,am_p){
ny = itm[bx].y;
nx = itm[bx].x;
get_m = itm[bx].v;
if(!mb[ny][nx].size()) continue;
fd(sj,,k){
fd(jq,,q){
np = get_p(itm[bx].r,itm[bx].b,itm[bx].g);
if(jq < np) break;
fd(xl,,r){
fo(sxl,,mb[ny][nx].size()-){
fo(sxh,,mb[ny][nx].size()-){
cta = mb[ny][nx][sxl];
ctb = mb[ny][nx][sxh];
ctm = d[ny][nx][cta] + *d[ny][nx][ctb];
if(xl < cta + ctb) continue;
if(sj < ctm) continue;
dp[sj][jq][xl] = max(dp[sj][jq][xl],dp[sj-ctm][jq-np][xl-cta-ctb] + get_m - np);
ans = max(dp[sj][jq][xl],ans); }
}
}
}
}
}
cout<<ans + q;
}
int main(){
input();
bfs();
get_ans();
return ;
}