[NOI2006]网络收费

题目背景

noi2006 day1t1

题目描述

网络已经成为当今世界不可或缺的一部分。每天都有数以亿计的人使用网络进行学习、科研、娱乐等活动。然而,不可忽视的一点就是网络本身有着庞大的运行费用。所以,向使用网络的人进行适当的收费是必须的,也是合理的。 MY 市NS 中学就有着这样一个教育网络。网络中的用户一共有$2^N$个,编号依次为1, 2, 3, …, $2^N$。这些用户之间是用路由点和网线组成的。用户、路由点与网线共同构成一个满二叉树结构。树中的每一个叶子结点都是一个用户,每一个非叶子结点(灰色)都是一个路由点,而每一条边都是一条网线(见下图,用户结点中的数字为其编号)。 ![](https://cdn.luogu.org/upload/pic/12807.png) MY 网络公司的网络收费方式比较奇特,称为“ 配对收费 ”。即对于每两个用户$i, j (1≤i < j ≤2^N )$ 进行收费。由于用户可以自行选择两种付费方式A、B中的一种,所以网络公司向学校收取的费用与每一位用户的付费方式有关。该费用等于每两位不同用户配对产生费用之和。 为了描述方便,首先定义这棵网络树上的一些概念: - 祖先:根结点没有祖先,非根结点的祖先包括它的父亲以及它的父亲的祖先; - 管辖叶结点:叶结点本身不管辖任何叶结点,非叶结点管辖它的左儿子所管辖的叶结点与它的右儿子所管辖的叶结点; - 距离:在树上连接两个点之间的用边最少的路径所含的边数。 对于任两个用户$i, j (1≤i

输入输出格式

输入格式


输入文件中第一行有一个正整数N。 第二行有$2^N$ 个整数,依次表示$1$ 号,$2$ 号,…,$2^N$ 号用户注册时的付费方式,每一个数字若为`0`,则表示对应用户的初始付费方式为A,否则该数字为`1`,表示付费方式为B。 第三行有$2^N$ 个整数,表示每一个用户修改付费方式需要支付的费用,依次为$C_1$, $C_2$, …,$C_M$。( M=$2^N$ ) 以下 $2^N$-1 行描述给定的两两用户之间的流量表F,总第(i + 3)行第j 列的整数为$F_{i, j+i}$ 。(1≤i<$2^N$,1≤j≤$2^N$ – i) 所有变量的含义可以参见题目描述。

输出格式


你的程序只需要向输出文件输出一个整数,表示NS 中学支付给网络公司的最小总费用。(单位:元)

输入输出样例

输入样例 #1

2
1 0 1 0
2 2 10 9
10 1 2
2 1
3

输出样例 #1

8

说明

【样例说明】 将 1 号用户的付费方式由B 改为A,NS 中学支付给网络公司的费用达到最小。 【数据范围】 40%的数据中$N≤4$; 80%的数据中$N≤7$; 100%的数据中$N≤10$,$0≤F_{i, j}≤500$,$0≤C_i≤500 000$。