Algorithms

There are N cities in a state. You start your ride from the first city.
You have to visit all other cities exactly once and finally return to your origin city. After visiting each city, you collect the analysis report.
But when you reached the last unvisited city, you remembered that you did not collect the report from city K. So, now you decide to first collect the report from city K and then return to your home city.
Given the distances between each pair of cities, you are required to find the shortest possible distance of your whole journey.

INPUT

The input begins with T (Number of test cases).
Second line contains K (City No. Where you forgot to collect the report).
Third line contains N (Number of cities).
Next there are N lines, line have exactly N numbers denoting distance from city I to all N cities.

OUTPUT

For each test case, print the Minimum Distance of total journey.
Answer for each test case should come in a new line.

CONSTRAINTS

 

You are given a number $$X$$. You have to obtain the number $$X$$ starting from 0 by performing the following operations:

• Add or subtract 1 to the current number. The cost is $$A$$ units.
• Double the current number. The cost is $$B$$ units.

Without making the number negative at any time, find the minimum cost of obtaining the number $$X$$ when starting from 0.

Note:
The Current number cannot be negative at any time.

Input format

• The first line consists of a number $$T$$(the number of test cases).
• Then $$T$$ lines follow and each line has $$3$$ space-separated integers $$X$$,$$A$$ and $$B$$.

Output format

Print $$T$$ lines where each line consists of $$1$$ integer denoting the minimum cost.

Constraints

You are given a cubic dice with 6 faces. All the individual faces have a number printed on them. The numbers are in the range of 1 to 6, like any ordinary dice. You will be provided with a face of this cube, your task is to guess the number on the opposite face of the cube.

Example 1: Example 2: