P4297 [NOI2006] 网络收费

noi2006 day1t1

网络已经成为当今世界不可或缺的一部分。每天都有数以亿计的人使用网络进行学习、科研、娱乐等活动。然而，不可忽视的一点就是网络本身有着庞大的运行费用。所以，向使用网络的人进行适当的收费是必须的，也是合理的。 MY 市 NS 中学就有着这样一个教育网络。网络中的用户一共有 $2^N$ 个，编号依次为 $1,2,3,\cdots,2^N$。这些用户之间是用路由点和网线组成的。用户、路由点与网线共同构成一个满二叉树结构。树中的每一个叶子结点都是一个用户，每一个非叶子结点（灰色）都是一个路由点，而每一条边都是一条网线（见下图，用户结点中的数字为其编号）。  MY 网络公司的网络收费方式比较奇特，称为“配对收费”。即对于每两个用户 $i,j$ $(1\leq i

输入文件中第一行有一个正整数 $N$。 第二行有 $2^N$ 个整数，依次表示 $1,2,\cdots,2^N$ 号用户注册时的付费方式，每一个数字若为 `0`，则表示对应用户的初始付费方式为 A，否则该数字为 `1`，表示付费方式为 B。 第三行有 $2^N$ 个整数，表示每一个用户修改付费方式需要支付的费用，依次为 $C_1,C_2,\cdots,C_{2^N}$。 以下 $2^N-1$ 行描述给定的两两用户之间的流量表 $F$，总共的第 $i+3$ 行第 $j$ 列的整数为 $F_{i,j+i}$。（$1\leq i

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

【样例说明】 将 $1$ 号用户的付费方式由 B 改为 A，NS 中学支付给网络公司的费用达到最小。 【数据范围】 $40\%$ 的数据中 $N\leq4$； $80\%$ 的数据中 $N\leq7$； $100\%$ 的数据中 $N\leq10,0\leq F_{i,j}\leq500,0\leq C_i\leq500000$。