Description

圣地历险记版本，kangaroo 们也获得了全新的泳装……要 kangaroo 去游泳是不是搞错了什么。当然，kangaroo 太多也不好，在这 $n\times n$ 的水池里面，每一个格子都被 kangaroo 占据了，来到水边的小 y 无处下脚，气得他决定搅动海水混起来！

小 y 施展了魔法，每一个格子上要么出现有向水流，要么直接生成一个漩涡，在有向水流上的 kangaroo 会被水流有向地送往其他格子，kangaroo 被送进漩涡或是推出水池后便会死亡，幸运的是，你现在手上还有诚信商家赠予的塞布，可以提前堵住至多 $m$ 处漩涡并让这里的水流不再运动（哪怕漩涡生成在 kangaroo 脚下，它也能被拯救），试着拯救尽可能多的 kangaroo 吧！

Input

第一行输入两个整数 $n, m$（$1\le n\le 1000, 0\le m\le n^2$）。

接下来 $n$ 行，每行读入一个长度为 $n$ 的字符串，代表水流状态（^ 代表向上，> 代表向右，v 代表向下，< 代表向左，@ 代表漩涡）。

Output

输出一个整数，表示最多能救下的 kangaroo 数量。

Samples

4 0
>v>v
^<^<
@@@@
v<>v

8

5 1
>>>>v
>>>vv
^>@vv
^^<<v
^<<<<

25

5 0
>>>>v
>>>vv
^>@vv
^^<<v
^<<<<

0

Note

对于第一个样例，第一二行的 kangaroo 一直顺水漂流都能活下来，所以答案是 $8$。

Resources

电子科技大学第十五届 ACM 趣味程序设计竞赛