说明

徐老师手上有一张藏宝图，宝藏的区域被分为 N*M 的矩形区域，每一个区域可能有若干宝藏，也可能没有宝藏，但有传送点可以传送到其它区域，这些区域里还有不可进入的，徐老师会从左上角，坐标 (0,0) 出发，可以选择向右走或者向下走，如果遇到传送点可以使用也可以不使用，注意徐老师无论如何也不能进入不可进入的区域，传送点允许多次使用。如果他在一个有宝藏的区域，他就会把宝藏取走，当然经过一个已经经过的地方就没宝藏可以再取了。他想知道自己最多可以收获多少宝藏。

输入格式

第一行输入两个整数 N,M\ (1 <= N,M <= 100) ，表示矩形区域行数和列数。

接下来 N 行，每行 M 个字符，数字 1-9 表示这个区域的宝藏数量，字符'*'表示这个区域是一个传送点，字符'#'表示这个区域不可进入。

接下来若干行，每行两个数字 x,y(0 <= x <= N-1,0 <= y <= M-1)表示地图从上往下从左往右每个传送点可以传送到的区域的坐标 (x,y)。

数据保证 (0,0) 区域一定不是'#'。

输出格式

输出一行，包含一个整数，表示徐老师可以收获的宝藏的最大值。

样例

3 3
12*
3#2
231
2 2

10