#P18856. [Croatian CPC2025] Brutalni Balatro

[Croatian CPC2025] Brutalni Balatro

Brutalni Balatro

题目描述

有 NN 张卡牌,第 ii 张卡牌有两个数值 chipsi\mathrm{chips}_i 和 multi\mathrm{mult}_i。

你需要恰好选择 KK 张卡牌。设选中的卡牌下标集合为 SS,这次选择的得分为

$$\left(\sum_{i\in S}\mathrm{chips}_i\right)\left(\sum_{i\in S}\mathrm{mult}_i\right).$$

求所有合法选择中的最小得分。

输入格式

第一行包含整数 TT,表示测试场景数。

每个场景包含三行:

  • 第一行包含整数 N,KN,K。
  • 第二行包含 NN 个整数 chips1,…,chipsN\mathrm{chips}_1,\ldots,\mathrm{chips}_N。
  • 第三行包含 NN 个整数 mult1,…,multN\mathrm{mult}_1,\ldots,\mathrm{mult}_N。

输出格式

对每个场景输出一行一个整数,表示最小得分。

数据范围

  • 1≤T≤1041\le T\le10^4,1≤K≤N≤10001\le K\le N\le1000。
  • 1≤chipsi,multi≤1061\le\mathrm{chips}_i,\mathrm{mult}_i\le10^6。
  • 同一场景中不存在两个数值都相同的两张卡牌。
  • 所有场景的 N2N^2 之和不超过 10610^6。

样例 1

输入

6
7 2
8 4 8 4 7 6 1
7 1 3 2 1 1 4
7 7
7 9 8 4 7 3 10
3 5 4 8 10 8 8
5 5
2 6 2 3 8
8 8 2 10 2
7 7
4 2 7 7 6 7 11
11 1 4 10 4 11 11
3 2
4 6 9
11 7 7
6 4
11 9 3 2 5 1
7 11 7 11 1 5

输出

20
2208
630
2288
180
264