题目描述

北境统领史塔克家族的部分家人被兰尼斯特家族软禁。为了营救家人，北境之王罗柏史塔克准备率领众多北境领主攻伐兰尼斯特家族。

北境共有 $n$ 个领主，每个领主都住在自己的城堡里面，每个城堡都屯有一定数量的士兵。由于地形、经济条件等原因，只有部分城堡之间有道路连接。罗柏史塔克想汇总领主的兵力，他可以选择从任一城堡出发，并沿着道路向后面的城堡进发（从第 $i$ 号城堡只能向第 $i+1$ 到第 $n$ 号城堡进发），当没有后续城堡时，完成兵力的集中。

请你设计一个汇总兵力的方案，使得罗柏史塔克能集中最多的兵力。

输入格式

有 $n+1$ 行。第 1 行只有一个数字，表示城堡的个数 $n$。第 2 行有 $n$ 个数，分别表示每个城堡中的士兵个数。第 3 行至第 $n+1$ 行表示城堡之间的道路连接情况，0 表示没有道路，1 表示有道路。如第 3 行有 $n-1$ 个数，表示第 1 个城堡至第 2 个、第 3 个、…、第 $n$ 个城堡是否有道路连接。后面以此类推。

输出格式

有两行数据。第一行表示最优方案中访问城堡序号的排列，各序号间以一个空格分隔，没有多余的空格。第二行只有一个数，表示能集中到的最多的士兵数量。

样例

输入数据#1

3  
100 150 200  
1 1  
0  

输出数据#1

1 3  
300

解释#1

最优方案：罗相·史塔克从 1 号城堡出发，然后到 3 号城堡，一共能集中 300 个士兵。

数据范围

$n \leq 20$，其他数据都在 int 范围以内。