Problem #1: 选地址(adress)

Problem #1: 选地址(adress)

Description
小X有很多朋友、、分布在N个城市。。
这N个城市之间,有些有直接的道路,有些是间接联通的(保证任何两个城市都可以相互到达。。)
但是、经过每条道路都是有代价的、、
于是。。
小X希望你来帮他找出一个城市,使得他的所有朋友到这个城市的代价最小。

【Input Format】
输入共2* n+1行,
其中第一行为一个整数N、
第2~N+1行
每行有N个整数、表示两个城市间的代价、(0表示不直接连通)
第n+2~2* N+1行
每行一个整数。表示每个城市中小X的朋友数。

【Output Format】
输出有两行。
第一行为你选中的城市
第二行为最小需要的代价。

Sample 1

Input

5
0 1 2 0 0 
1 0 0 0 20
2 0 0 10 0
0 0 10 0 1
0 20 0 1 0
2
3
4
5
6

Output

4
109

Limitation

1s, 128MiB for each test case.
Data Limit
对于100%的数据,n<=200,输出保证不超过longint