题目描述

背景

如今，街道上有许多汽车、摩托车、卡车和其他车辆需要进行翻新。你接下了这份工作，并顺便从一家大型电视台那里赚了一些钱。

当然，工作量很大，你觉得一个人难以完成。因此，你决定将喷漆、内饰装饰等工作交给不同的修理厂来完成。然而，这些修理厂非常专业化，不同的工作需要不同的修理厂来完成。更麻烦的是，修理厂的收费会根据车辆的整体状况而增加。例如，如果车辆的内饰是全皮革的，喷漆工人可能会收取更高的费用。由于这些“附加费”取决于已经完成的工作，你目前正在尝试通过找到最优的工作顺序来节省开支。

问题

每个工作编号为$1$到$n$。给定每个工作的基础价格$p$，以及每对工作($i, j$)（$i ≠ j$）的附加费$s$（以美元计），这意味着如果工作$j$在工作$i$之前完成，那么完成工作i时需要额外支付$s$美元。你需要计算完成所有工作的最小总成本。

输入

第一行包含测试用例的数量。每个测试用例的第一行是一个整数$n（1 ≤ n ≤ 14）$，表示工作的数量。接下来的n行，每行包含n个整数。第i行的第i个整数是工作i的基础价格，第$j$个整数$（j ≠ i）$是如果工作j在工作i之前完成时需要支付的附加费。所有价格均为非负整数且不超过$100000$。

输出

对于每个测试用例，首先输出一行"$Scenario$ #$i$:"，其中$i$是测试用例的编号（从$1$开始）。然后输出一行：

"$You$ $have$ $officially$ $been$ $pimped$ $for$ $only$ $p$"

其中$p$是最小的总价格。每个测试用例的输出后跟一个空行。

输入样例

2
2
10 10
9000 10
3
14 23 0
0 14 0
1000 9500 14

输出样例

Scenario #1:
You have officially been pimped for only $30

Scenario #2:
You have officially been pimped for only $42

题目来源

TUD Programming Contest 2005, Darmstadt, Germany