#CW45. MEX(mex)

MEX(mex)

题目描述

小 W 有一个长度为 nn 的正整数数组 aa。定义数组的 mex 为没有在数组中出现的最小正整数。

一次操作可以选择一个下标 ii 和一个整数 xx,满足 1≤i≤n1\le i\le n 且 0≤x<ai0\le x<a_i,支付 xx 的代价并把 aia_i 改为 ai−xa_i-x。操作可以进行任意次。

请计算使数组的 mex 恰好等于 kk 所需的最小总代价。如果无法做到,输出 −1-1。

输入格式

第一行一个正整数 TT,表示测试数据组数。

接下来每组数据包含两行:

  • 第一行两个整数 n,kn,k;
  • 第二行 nn 个正整数 a1,a2,…,ana_1,a_2,\dots,a_n。

输出格式

对于每组数据输出一行一个整数,表示最小总代价;无解时输出 −1-1。

样例 1 输入

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

样例 1 输出

2
1
5
1

数据范围

对所有数据,保证 1≤T≤10001\le T\le 1000,1≤n,k≤2×1051\le n,k\le 2\times 10^5,∑n≤106\sum n\le 10^6,且 1≤ai≤1091\le a_i\le 10^9。

本题采用捆绑测试并开启子任务依赖。只有某个子任务中的所有测试数据以及它所依赖的子任务均通过时,才能获得该子任务的分数。

子任务 分值 测试点 附加限制 依赖
1 25 1∼51\sim 5 n≤8n\le 8 无
2 6∼106\sim 10 所有 aia_i 两两不同
3 11∼1511\sim 15 n≤500n\le 500 1, 2
4 16∼2016\sim 20 无附加限制 1, 2, 3