时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
有堆石子，第i堆石子的石子数量是
，作为牛客网的一头领头牛，牛牛决定把这些石子搬回牛客。如果牛牛一次搬运的石子数量是
，那么这堆石子将对牛牛产生
的负担值。牛牛最多只能搬运
次，每次搬运可以从一堆石子中选出一些石子搬回牛客，每次搬运不能同时从两堆石子中选取石子，每次只能搬运整数个石子。牛牛是一只聪明的牛，他想出了一种搬运计划可以最小化他搬运完这些石子的负担值的总和，但是突然牛牛的死敌牛能出现了，牛能每次可以施展以下的魔法：
将第
堆石子的数量变为
这打乱了牛牛的计划，每次牛能施展一次魔法，牛牛就得重新规划他的搬运方案，但是牛能施展魔法的次数太多了，牛牛根本忙活不过来了，于是他请来了聪明的你帮他写一个程序计算。
输入描述:
第一行两个整数
第二行n个整数
第三行一个整数，表示牛能施展魔法的次数
接下来
，表示牛能将第
输出描述:
输出包含q行，每行输出一个整数表示在牛能施展魔法后，牛牛搬完所有n堆石子所产生最小化的负担值的总和。