#P12258. [蓝桥杯 2024 国 Java B] 背包问题

[蓝桥杯 2024 国 Java B] 背包问题

题目描述

神奇商店中一共有 NN 种不同的物品,第 ii 种物品的重量为 WiW_i,每种物品的数量都是无限个。店主会从中挑选任意种商品,每种商品可以选择任意个并将其装入到一个背包之中,从而可以组合出多种背包(这个背包可以容纳无限多的物品),其中背包的重量就是其中所含物品的重量之和。

小蓝想要的背包中至少要有 KK 件物品。小蓝想要知道,在所有满足他要求的背包中,如果将背包重量从小到大排序并去除重复的重量,排名第 LL 的重量是多少。

输入格式

第一行输入三个整数,用空格分隔,依次是 NNKKLL

第二行输入 NN 个用空格分隔的整数表示 NN 件物品的重量。

输出格式

输出一行,包含一个整数表示答案。

7 2 7
84 21 12 3 65 5 41
13

提示

样例说明

背包中物品个数大于等于 22 时,从小到大依次出现的背包重量为:

6=3+36 = 3 + 38=3+58 = 3 + 59=3+3+39 = 3 + 3 + 310=5+510 = 5 + 511=3+3+511 = 3 + 3 + 512=3+3+3+312 = 3 + 3 + 3 + 313=3+5+513 = 3 + 5 + 5

评测用例规模与约定

  • 对于 40%40\% 的评测用例,1Wi1001 \leq W_i \leq 1001L101 \leq L \leq 10
  • 对于 100%100\% 的评测用例,1N101 \leq N \leq 101K101 \leq K \leq 101Wi1091 \leq W_i \leq 10^91L1051 \leq L \leq 10^5