背景

PLQ在考场上发现了一个严峻的问题:他边上的人在打小抄!他十分生气:这个人怎么可以这样呢!正义感涌入心头,他决定向老师报告。当他抬头一望,顿感失望,茫茫人海后,老师正在呼呼的睡大觉。PLQ感到自己的人生观价值观世界观都被打击了。但是,他绝不会放纵这种行为,他要传字条给老师。“哼哼,你完了,零分走你的。”PLQ在心里暗暗地想着。

描述

给出考场中每个学生的信息a,若a=0则这名学生与作弊的学生关系较好,决不能传给他;若a>0则a为这名学生的损人值。为了万无一失,一定要找一条损人值最小的路。所谓损人值最小的路,是沿途中所有学生的损人值之和最小的路(不包括PLQ)。当然,每个学生都只能向自己前后左右的学生传,包括万能的PLQ。这时PLQ又意识到一个问题:考场里的学生几乎数不清,他该怎么传呢?于是他看着呼呼大睡的老师,心生一计:“就破一次例吧,请场外援助。”他立即发短信给你,向你求助。

另外,设老师的坐标为(0,0),且只能由(1,1)这名学生传给老师。

你只需要输出一个数,若这张字条无法传给老师则输出-1,否则输出损人值最小的路的总损人值。

输入格式

有m+1行,第一行有四个用空格隔开的数m、n、x、y,m和n表示考场的尺寸,也就是考场的长和宽,x和y表示PLQ所在的坐标。接下来的m行,每行有n个自然数,这n个自然数都用空格隔开,均为考场上各个学生的信息。

输出格式

只有一行,这一行只有一个整数,为所要输出的数。

样例输入

4 5 4 5

100 0 120 0 200

40 30 60 60 70

20 10 20 20 0

10 200 20 20 30000

样例输出

230

数据范围与约定

20%的数据,0<m,n≤5。

50%的数据,0<m,n≤10。

60%的数据,0<m,n≤30。

80%的数据,0<m,n≤100。

100%的数据,0<m,n≤300,0≤a≤1000,0<x≤m,0<y≤n,与考试作弊的人关系好的考生≤总人数×30%。

样例解释

传递路径为:

(4,5)->(4,4)->(3,4)/(4,3)->(3,3)->(3,2)->(3,1)->(2,1)->(1,1)