I-礼物商店_第二届“重科杯”重庆科技大学程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

六一儿童节要到了，小明想给班上的同学买一些礼物送给大家。小明的购物清单有 $m$ 件商品，小明一共需要买 $n$ 件商品，但每件商品都有限制购买次数，第 $i$ 件商品最多买 $a_i$ 次。

为了买礼物，小明来到一家很坑的商店：这个商店每卖出一件商品，其商品价格会发生神秘的变化，并且这家商店每次只会出售一件商品。

每件商品都有一个初始价格 $x_i$ ，同时商家设计了一个神秘的算法:

假设你购买的商品是第 $i$ 件，其价格为 $x$ ，那么在其购买后，下次购买该件商品的价格会发生如下变换：

$x\to (x+k)\ |\ (x\ \&\ k)$

由于时间紧迫，小明只能无奈的在这里购买，问小明最少花多少钱能买到 $n$ 件商品。

输入描述:

第  行，输入  个正整数 ，表示小明需要的商品数量，以及购物清单上的  件商品，以及参数 。

第  行，输入  个数 ，表示第  件商品限制的购买次数。

第  行，输入  个数 ，表示第  件商品的初始价格。

数据保证 。

输出描述:

请你输出小明最少花多少钱可以买到  件商品。

示例1

输入

复制

2 3 1
1 1 1
5 8 3

输出

复制

说明

显然买一次第  种物品和买一次第  种物品即可，花费  元。