No submission language available for this problem.

Background

Special for beginners, ^_^

Description

设有 $n \times n$ 的方格图,每个格子均为一个正整数。

某人从图的左上角的 $A$ 点 $(1,1)$ 出发，可以向下行走，也可以向右走，直到到达右下角的 $B$ 点 $(n,n)$。在走过的路上，他可以取走方格中的数。但是方格中有 $k$ 个位置被封锁，因此这个人不能到达这 $k$ 个位置。

此人从 $A$ 点到 $B$ 点，试找出一条路径，使得取得的数之和为最大，如果不能到达 $B$ 点，请输出 $0$。

Format

Input

第一行两个整数 $n,k(1 \leq n \leq 1000,0 \leq k \leq 1e5)$.

接下来 $n$ 行，每行 $n$ 个正整数 $a_{i,j}(1 \leq a_{i,j} \leq 1e9)$.

接下来 $k$ 行，每行两个整数 $x,y(1 \leq x,y \leq n)$，表示 $(x,y)$ 位置被封锁.

数据保证(1,1)位置没有被封锁,注意一个位置可能多次封锁

Output

输出一个整数，表示从 $A$ 到 $B$ 取得的数之和的最大值，如果不能到达 $B$ 点，请输出 $0$。

Samples

2 1
1 2
3 4
2 1

7

2 1
1 2
3 4
2 2

0

样例一解释

$(1,1)->(1,2)->(2,2)$，路径和为 $1+2+4=7$

Limitation

1s, 1024KiB for each test case.