← 返回题目列表

AtCoder · discovery_2016_final_b

B. DDPC特别自助餐II

中文机器翻译题面 查看原题

問題文

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 。
  • 这种情况不满足部分点相加约束。