You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在一次紧急军事行动中，你是特种部队的精英战士，接到了一项绝密任务。你所在的部队接到情报，小卓被敌军俘虏了，小卓掌握着一种能改变战局的关键技术，必须立即营救，以确保战斗胜利。 敌军区域由一个复杂的 $n \times n$ 网格构成，每个格子代表一个不同的区域，区域内可能有敌军巡逻、障碍和防御工事。每个格子中的数值表示穿越该区域所需的花费。你必须从起始点 $(0, 0)$ 出发，穿越敌人的防线，成功解救被关押在 $(r, c)$ 的小卓，并在限定的花费 $k$ 内，安全撤离到目的地 $(n-1, n-1)$，为了避免被敌人发现，每一个地点只能去一次。现在你能在不超过限定花费下成功完成任务吗？可以的话，最小花费是多少呢?

敌军的布防极为严密，随时可能对你展开攻击。你需要在穿越过程中避开敌军巡逻，克服重重障碍，保持隐蔽，确保任务的成功完成。途中，你需要合理规划每一步的行动，尽量减少不必要的花费和时间浪费，确保自己和小卓的安全。

输入格式

第一行为4个整数：$n \:$$(1 ≤ n ≤ 10)$, $k \:$ $(1 ≤ k ≤ 10000)$, $r, c$ $(0 ≤ r, c < n)$ ,分别表示敌军区域的行数（列数), 限定花费，小卓的坐标 $(r, c)$。

第二到 $N + 1$ 行是一个二维数组 $grid$ $(1 ≤ grid[i][j] ≤ 100)$，表示敌军区域中每个格子的花费。

输出格式

一个整数，表示满足条件的最小花费，如果不能在限定花费内完成任务请输出 -1。

样例输入输出

3 9 1 1
1 2 3
2 2 2
1 0 4

9