牛牛流浪大陆的时候偶然间发现了一个地图和k把钥匙,地图上标出了一些宝藏的位置。 一把钥匙可以开启一个宝藏,获得该宝藏里面的金币,钥匙使用后会被损坏无法再次使用,一个位置(i,j)可能有多个宝藏,但是一个位置只能使用一把钥匙。 因为牛牛是一个精通传送术的流浪者,所以他一步可以走很远。但是他不会走回头路,也不会在一块地方停留。 换言之,如果牛牛当前位于第i行第j列,那么他下一步的位置的行号的范围是[i+1,inf),列号的范围是[j+1,inf)。inf代表无穷大 牛牛最开始位于位置(0,0) 现在牛牛想知道,他最多可以获得多少金币。
示例1

输入

3,3,[1,2,3],[2,1,2],[3,2,2]

输出

4

说明

牛牛一共有三把钥匙,他可以开启(1,2)处的宝藏获得3个金币,但是之后无法再走到有金币的位置
他也可以先开启(2,1)处的宝藏获得2个金币,再开启(3,2)处的宝藏获得2个金币,总共获得4个金币。

备注:
第一个参数n代表宝藏的个数第二个参数k代表钥匙个数第三个参数x包含n个元素,代表n个宝藏的行号第四个参数y包含n个元素,代表n个宝藏的列号第五个参数a包含n个元素,代表n个宝藏内的金币数量。
加载中...