logo AlgoBeat OnlineJudge
登录 注册

#104069. [BZOJ 4069] [Apio2015]巴厘岛的雕塑

内存限制:64 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

印尼巴厘岛的公路上有许多的雕塑,我们来关注它的一条主干道。

在这条主干道上一共有 座雕塑,为方便起见,我们把这些雕塑从 连续地进行标号,其中第 座雕塑的年龄是 年。为了使这条路的环境更加优美,政府想把这些雕塑分成若干组,并通过在组与组之间种上一些树,来吸引更多的游客来巴厘岛。

下面是将雕塑分组的规则:

这些雕塑必须被分为恰好 组,其中 ,每组必须含有至少一个雕塑,每个雕塑也必须属于且只属于一个组。同一组中的所有雕塑必须位于这条路的连续一段上。

当雕塑被分好组后,对于每个组,我们首先计算出该组所有雕塑的年龄和。

计算所有年龄和按位取或的结果。我们这个值把称为这一分组的最终优美度。

请问政府能得到的最小的最终优美度是多少?

备注:将两个非负数 按位取或是这样进行计算的:

首先把 转换成二进制。

的二进制位数, 的二进制位数, 中的最大值。 的二进制表示为 的二进制表示为 ,其中 分别是 二进制表示下的第 位,第 位是数的最高位,第 位是数的最低位。

按位取或后的结果是: 。其中:

输入格式

输入的第一行包含三个用空格分开的整数

第二行包含 个用空格分开的整数

输出格式

输出一行一个数,表示最小的最终优美度。

样例

样例输入 #1

6 1 3
8 1 2 1 5 4

样例输出 #1

11

样例解释

将这些雕塑分为 组,,它们的和是 ,最终优美度是 。(不难验证,这也是最终优美度的最小值。)

数据范围与提示

子任务 1 (9 分)

子任务 2 (16 分)

子任务 3 (21 分)

子任务 4 (25 分)

子任务 5 (29 分)