提示: 欢迎访问OurACM平台。
Problem 2092 收集水晶

Accept: 135    Submit: 551
Time Limit: 5000 mSec    Memory Limit : 32768 KB

Problem Description

shadow来到一片神奇的土地,这片土地上不时会出现一些有价值的水晶,shadow想要收集一些水晶带回去,但是这项任务太繁杂了,于是shadow让自己的影子脱离自己并成为一个助手来帮助自己收集这些水晶。

shadow把这片土地划分成n*m个小方格,某些格子会存在一些shadow和他的影子都无法穿越的障碍,比如巨石、树木、野兽等。shadow预先探测到了水晶出现的时间、位置以及它们的价值,但这些水晶的存在就如昙花一现般短暂,若在出现后1秒内没有收集到,它便将消失。

在第0秒的时候,shadow和他的影子都处在第一行第一列的格子上,shadow和他的影子可以相互独立的移动,互不干扰。每一秒shadow能移动到相邻的一格,也可以呆在原地不动,shadow的影子也是。那么,shadow和他的影子能收集到的水晶价值总和最大是多少呢?

Input

输入数据第一行包含一个整数T,表示测试数据的组数。对于每组测试数据:

第一行两个整数n、m( 2 <= n , m <= 10 ),表示土地被划分为n行,每行m列个小方格。

接下来n行,每行m个字符,’.’或者’#’, 描述土地信息,’.’表示空地,’#’表示障碍。

接下来一行包含一个整数p( p < 0 < 1000 ),表示总共会出现的水晶数量。

接下来p行,每行4个整数,t( 0 < t <= 200 ),x( 1 <= x <= n ),y( 1 <= y <= m ),v( 0 < v <= 1000 ),表示第t秒会有一个价值v的水晶出现在第x行第y列的格子里。

Output

对于每组测试数组,输出一行包含一个整数,表示shadow和他的影子能收集到的最大价值总和。

Sample Input

1 3 3 ... ..# ... 3 2 3 1 3 2 2 2 2 2 1 3 1

Sample Output

5

Source

福州大学第九届程序设计竞赛

Submit  Back  Status  Discuss