【2021】360春招编程题（第一批）

小马最近找到了一款打气球的游戏。

每一回合都会有 n个气球，每个气球都有对应的分值，第 i个气球的分值为a_i。

这一回合内，会给小马两发子弹，但是由于小马的枪法不准，一发子弹最多只能打破一个气球，甚至小马可能一个气球都打不中。

现给出小马的得分规则：

1. 若小马一只气球都没打中，记小马得0分。

2. 若小马打中了第 i只气球，记小马得a_i 分。

3. 若小马打中了第 i只气球和第 j只气球（i<j），记小马得 a_i|a_j分。

（其中| 代表按位或，按位或的规则如下：

现在请你计算所有情况下小马的得分之和。

第一行，一个整数n，表示此回合的气球数量。

第二行，用空格分开的n 个整数，第i个整数为a_i，表示每个气球对应的分值。

对于其中60% 的数据， 1≤n≤1000, 1≤a_i≤100000

对于另外 40% 的数据，  1≤n≤50000, 1≤a_i≤100000

一行一个整数，代表所有情况下小马的得分之和。

X星人发现了一个藏宝图，在藏宝图中标注了N个宝库的位置。这N个宝库连成了一条直线，每个宝库都有若干枚金币。

X星人决定乘坐热气球去收集金币，热气球每次最多只能飞行M千米（假设热气球在飞行过程中并不会发生故障）此外，由于设计上的缺陷，热气球最多只能启动K次。

X星人带着热气球来到了第1个宝库（达到第1个宝库时热气球尚未启动），收集完第1个宝库的金币后将启动热气球前往下一个宝库。如果他决定收集某一个宝库的金币，必须停下热气球，收集完之后再重新启动热气球。当然，X星人每到一个宝库是一定会拿走这个宝库所有金币的。

已知每一个宝库距离第1个宝库的距离（单位：千米）和宝库的金币数量。

请问X星人最多可以收集到多少枚金币？

单组输入。

第1行输入三个正整数N、M和K，分别表示宝库的数量、热气球每次最多能够飞行的距离（千米）和热气球最多可以启动的次数，三个正整数均不超过100，相邻两个正整数之间用空格隔开。

接下来N行每行包含两个整数，分别表示第1个宝库到某一个宝库的距离（千米）和这个宝库的金币枚数。（因为初始位置为第1个宝库，因此第1个宝库所对应行的第1个值为0。）

输入保证所有的宝库按照到第1个宝库的距离从近到远排列，初始位置为第1个宝库。

输出一个正整数，表示最多可以收集的金币数。