题目描述

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

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

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

输入格式

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

输出格式

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

样例

3
100 150 200
1 1
0

1 3
300

解释#1

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

数据范围

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