James Moriarty started fire at M places in London. Sherlock Holmes has been called to help extinguish the fires as quickly as possible. There are exactly N fire stations in the city, each having infinite amount of fire trucks. But the time taken by each fire station to fill a truck is different and the fire stations can only fill one truck at a time. Initially all the fire trucks are empty.

Given the time taken by each fire station to fill one truck and the time taken for a fire truck to reach the j^thplace from the i^th fire station, Sherlock needs to tell the minimum time taken to extinguish the fire at all places.

Input

First line contains T,(T

Each line of first test case contains two integers N and M,(N,M

Next line contains N space separated integers, where the i^th integer denotes the time taken (1^th fire station to fill one truck.

Then next N lines will follow, each containing M integers, where the integer at i^th row and j^th column denotes the time taken (1^th fire station to reach j^th place.

Output

Output of each test case is a single line denoting the minimum time required to extinguish the fire completely.

Note

Consider that as soon as a fire truck reaches the place, the fire extinguishes there in no time.

Each place will require exactly one truck to extinguish the fire.

Fire truck once used can not be used again.

There are infinite number of fire trucks at every station.

Example

Input: 1 3 4 2 5 4 1 2 3 1 2 3 1 2 2 2 3 1 Output: 6

Explanation:

The 1^st fire station sends trucks to both 1^st and 4^th place. Time Taken=5

The 2^nd fire station sends a truck to 3^rd place. Time Taken=6

The 3^rd fire station sends a truck to 2^nd place. Time Taken=6