問題文
DISCO呈现探索频道节目大赛2016 DDPC特别自助餐时间已经开始。你正要把食物放在一个没有食物的托盘上。 DDPC特色自助餐 N 有不同类型的菜肴。 i 菜品种类是从自助餐开始就开始的。 T_i 几秒钟就消失了,食物的美味消失了。 A_i 。
DDPC 特别自助餐有一些特殊规则。
- 你 1 将不同种类的食物放在托盘上。 1 你必须花几秒钟。换句话说,就是你开始放食物的时间 s ,食物吃完的时间是 s+1 。
- 托盘上不得放置与先前放置的相同类型的食物。
- 当前时间 当 s 被给予s+1≦T_i 不满足时,类型 i 食物不能放在托盘上。
你是托盘上食物美味的总和。 X 之后,我决定回到座位上。托盘上食物的美味总和 可以大于或等于 X 的最小时间 t 。
入力
输入将以以下格式从标准输入给出。
N X T_1 T_2 … T_N A_1 A_2 … A_N
- 1 一个整数,表示该行DDPC特色自助餐中存在的菜品种类数量 N(1≦N≦10^{5}) 以及托盘上菜肴的美味度总和的目标值。 X(1≦X≦10^{9}) 用空格分隔。
- 2 DDPC特色自助餐已上线的菜品 i 该种食物用完的时间 T_i (1≦T_i≦10^{5}) 用空格分隔。
- 3 DDPC特色自助餐已上线的菜品 i 代表菜肴类型美味程度的整数 A_i (1≦A_i≦10^{5}) 用空格分隔。
出力
托盘上食物的美味程度总和
在 X 的最小时间 t 它可以有多少种方式表示为 1 行输出。如果不可能
输出-1。不要忘记最后的换行符。
当
部分点
针对此问题设置了部分分数。 如果正确答案是满足
- T_i<T_j 时, 如果正确答案是满足A_i≧A_j 的数据集 10 点。 如果正确答案是满足
- 如果答案对于没有附加约束的数据集是正确的,则进一步 40 获得的总积分 获得 50 点。
入力例 1
4 5 1 2 3 4 3 3 1 1
出力例 1
2
- 通过按如下方式准备食物,您可以 2 是托盘上菜肴的美味总和。 5 或更多是可能的。
- 0 第二点托盘上食物的美味程度总和为 0 。类型 将 1 食物放在托盘上。
- 1 第二点托盘上食物的美味程度总和为 3 。类型 将 2 食物放在托盘上。
- 2 第二点托盘上食物的美味程度总和为 6 。
- 这种情况满足部分点相加约束。
入力例 2
3 10 1 2 3 3 3 4
出力例 2
3
- 通过按如下方式准备食物,您可以 3 是托盘上菜肴的美味总和。 10 或更多是可能的。
- 0 第二点托盘上食物的美味程度总和为 0 。类型 将 1 食物放在托盘上。
- 1 第二点托盘上食物的美味程度总和为 3 。类型 将 2 食物放在托盘上。
- 2 第二点托盘上食物的美味程度总和为 6 。类型 将 3 食物放在托盘上。
- 3 第二点托盘上食物的美味程度总和为 10 。
- 这种情况不满足部分点相加约束。
入力例 3
3 5 9 9 4 2 2 6
出力例 3
1
- 通过按如下方式准备食物,您可以 1 是托盘上菜肴的美味总和。 5 或更多是可能的。
- 0 第二点托盘上食物的美味程度总和为 0 。类型 将 3 食物放在托盘上。
- 1 第二点托盘上食物的美味程度总和为 6 。
- 这种情况满足部分点相加约束。
入力例 4
5 101 1 2 3 4 5 20 20 20 20 20
出力例 4
-1
- 无论你如何准备食物,托盘上食物的美味总和 它不能大于 101 。
- 这种情况满足部分点相加约束。
入力例 5
2 2 1 1 1 1
出力例 5
-1
- 時刻 0 无论您选择哪道菜,其他菜都会同时进行。 1 ,所以无法欣赏托盘上食物的美味。 2 。
- 这种情况满足部分点相加约束。
入力例 6
4 6 1 1 2 2 3 4 1 2
出力例 6
2
- 通过按如下方式准备食物,您可以 2 是托盘上菜肴的美味总和。 6 或更多是可能的。
- 0 第二点托盘上食物的美味程度总和为 0 。类型 将 2 食物放在托盘上。
- 1 第二点托盘上食物的美味程度总和为 4 。类型 将 4 食物放在托盘上。
- 2 第二点托盘上食物的美味程度总和为 6 。
- 这种情况满足部分点相加约束。
入力例 7
3 4 1 2 2 1 2 2
出力例 7
2
- 通过按如下方式准备食物,您可以 2 是托盘上菜肴的美味总和。 4 或更多是可能的。
- 0 第二点托盘上食物的美味程度总和为 0 。类型 将 2 食物放在托盘上。
- 1 第二点托盘上食物的美味程度总和为 2 。类型 将 3 食物放在托盘上。
- 2 第二点托盘上食物的美味程度总和为 4 。
- 这种情况不满足部分点相加约束。