#P4250. [PA2014]Bazarek

    ID: 3467 传统题 1000ms 256MiB 尝试: 64 已通过: 35 难度: 4 上传者: 标签>难度分类普及+/提高-贪心排序贪心交换论证构造与建模奇偶性分析排序与序列处理一维前缀和前后缀最值CF1600

[PA2014]Bazarek

[PA2014] Bazarek

题目描述

小巴伊泰克在外婆家过暑假。外婆每天去集市买东西,每种商品最多买一件,并且总是花奇数金额。集市上有 nn 种商品,各有一个固定价格。

外婆要买恰好 kk 件商品,却没有告诉巴伊泰克打算买哪几件。他需要算出外婆至少要带多少钱,才能买下任意一组符合要求的商品。也就是在恰好选择 kk 种商品且总价为奇数的方案中,求最大的总价。对每一天分别回答。

输入格式

第一行一个整数 nn,表示商品种数。

第二行 nn 个整数 a1,…,ana_1,\ldots,a_n,分别表示各商品的价格。第三行一个整数 mm,表示询问天数。

接下来 mm 行,每行一个整数 kik_i,表示第 ii 天要买的商品件数。

输出格式

输出 mm 行。对于第 ii 天,输出恰好选择 kik_i 种商品所能得到的最大奇数总价。如果这样的方案不存在,输出 -1。

样例 #1

样例输入 #1

4
4 2 1 3
3
2
3
4

样例输出 #1

7
9
-1

样例说明

买两件时最大奇数总价为 4+3=74+3=7,买三件时为 4+3+2=94+3+2=9。买四件时只能买下全部商品,总价为 1010,所以输出 -1。

数据规模与约定

1≤n,m≤1061\le n,m\le10^6,1≤ai≤1091\le a_i\le10^9,1≤ki≤n1\le k_i\le n。

题目来源见 Potyczki Algorytmiczne 2014 原题.