今天的考试题。
考试的时候因为以前做过还写过题解，然后就以为模型已经很清楚了，然后就开始直接推。最后因为蜜汁自信一定能推出来，然后模型搞错了，只能交个暴力上去，于是这场考试GG。
第一次碰上这道题是在去湖南省选集训的时候，当时非常naive的没看出来这是个最小割的模型。后来那人讲明白了，恍然大悟，然后慢慢的就又忘了。当时第一次遇到这道题而且AC的只有一个人。
所以如果没有碰到过这道题，模型确实很难看出来。
首先对于每个射手，分为两类，一是上下的，二是左右的，因为只有这样才存在射程相交的情况，也就是我们要着重判断的情况。
先考虑最简单的，对于方向平行的射手，只需要取射程中最大的，但是最小割怎么求最大呢？变成相反数加一个偏移值即可。
再来考虑相交的，我们要处理这样一种情况，就是对于两个射程相交分开的两个部分，割了其中一个部分就不能割另一个射程的相应部分。但是这样着实不好处理，考虑把横纵射程分开，纵射程倒着来。
然后把横纵相交的点拆成两个点，分属于横纵两个射程，然后在这两个点之间连一条容量为$\infty$的边。
为什么这样处理，画画图就能看明白了，不做具体解释。
另外，具体处理中还有很多细节，需要注意。
//archery
//by Cydiater
//2017.1.19
#include <iostream>
#include <queue>
#include <map>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <string>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <bitset>
#include <set>
#include <vector>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define Auto(i,node) for(int i=LINK[node];i;i=e[i].next)
#define FILE "archery"
const int MAXN=2505;
const int oo=0x3f3f3f3f;
const int Delta=20;
int N,M;
int LINK[MAXN<<1],len=0,dx[MAXN],dy[MAXN],top=0,ID[MAXN][MAXN][2],cnt=0,walked[MAXN][MAXN],Val[MAXN<<1],ans=0,level[MAXN<<1],q[MAXN<<10],head,tail,S,T;
char s[MAXN][MAXN];
struct edge{
int y,next,flow,reverse;
}e[MAXN<<10];
namespace solution{
inline void insert(int x,int y,int flow,int delta){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].flow=flow;e[len].reverse=len+delta;}
bool Walk(int x,int y){
char ch=s[x][y];
int tx=x,ty=y;
bool flag=0;
while(tx>=1&&tx<=N&&ty>=1&&ty<=M){
if(s[tx][ty]>='1'&&s[tx][ty]<='9'){
flag=1;
break;
}
tx+=dx[ch];ty+=dy[ch];
}
if(!flag)return 0;
tx=x;ty=y;
while(tx>=1&&tx<=N&&ty>=1&&ty<=M){
walked[tx][ty]++;
tx+=dx[ch];ty+=dy[ch];
}
return 1;
}
void reWalk(int x,int y,bool tag){
char ch=s[x][y];
int tx=x,ty=y;
while(walked[tx][ty]){
if(walked[tx][ty]==2) q[++top]=ID[tx][ty][tag];
else if(s[tx][ty]>='1'&&s[tx][ty]<='9') q[++top]=ID[tx][ty][0];
tx+=dx[ch];ty+=dy[ch];
}
}
void Prepare(){
cin>>N>>M;
dx['A']=-1;dy['A']=0;
dx['V']=1;dy['V']=0;
dx['>']=0;dy['>']=1;
dx['<']=0;dy['<']=-1;
up(i,1,N)scanf("%s",s[i]+1);
S=++cnt;T=++cnt;
up(i,1,N)up(j,1,M){
ID[i][j][0]=++cnt;
ID[i][j][1]=++cnt;
if(s[i][j]>='1'&&s[i][j]<='9')
Val[cnt]=Val[cnt-1]=s[i][j]-'0';
}
up(i,1,N)up(j,1,M)if(s[i][j]=='>'||s[i][j]=='<'||s[i][j]=='A'||s[i][j]=='V')
if(Walk(i,j))ans+=Delta;
up(i,1,N)up(j,1,M)if(s[i][j]=='>'||s[i][j]=='<'){
top=0;q[++top]=S;
reWalk(i,j,0);
q[++top]=T;
if(top>2)up(i,2,top){
insert(q[i-1],q[i],Delta-Val[q[i-1]],1);
insert(q[i],q[i-1],0,-1);
}
}
up(i,1,N)up(j,1,M)if(s[i][j]=='A'||s[i][j]=='V'){
top=0;q[++top]=T;
reWalk(i,j,1);
q[++top]=S;
if(top>2)down(i,top-1,1){
insert(q[i+1],q[i],Delta-Val[q[i]],1);
insert(q[i],q[i+1],0,-1);
}
}
up(i,1,N)up(j,1,M)if(walked[i][j]==2){
insert(ID[i][j][0],ID[i][j][1],oo,1);
insert(ID[i][j][1],ID[i][j][0],0,-1);
}
}
bool makelevel(){
memset(level,-1,sizeof(level));
head=1;tail=0;q[++tail]=S;
level[S]=0;
for(;head<=tail;head++){
int node=q[head];
Auto(i,node)if(e[i].flow&&level[e[i].y]==-1){
level[e[i].y]=level[node]+1;
q[++tail]=e[i].y;
}
}
return level[T]!=-1;
}
int addflow(int node,int flow){
if(node==T) return flow;
int d,maxflow=0;
Auto(i,node)if(e[i].flow&&level[e[i].y]==level[node]+1)
if(d=addflow(e[i].y,min(e[i].flow,flow-maxflow))){
maxflow+=d;
e[i].flow-=d;
e[e[i].reverse].flow+=d;
}
if(maxflow==0)level[node]=-1;
return maxflow;
}
void Dinic(){
int d;
while(makelevel())
while(d=addflow(S,oo))
ans-=d;
}
}
int main(){
freopen(FILE".in","r",stdin);
//freopen(FILE".out","w",stdout);
using namespace solution;
Prepare();
Dinic();
cout<<ans<<endl;
return 0;
}