← 返回题目列表

Codeforces · 222/D

D. 奥林匹克竞赛

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

一个名叫 Vasya 的男孩参加了奥林匹克运动会。他的老师知道瓦夏在两次奥运会巡回赛中总共至少获得了 x 分。老师有第一届和第二届奥赛的成绩,但问题是,成绩只有分数,没有名字。老师必须知道瓦夏的机会。

帮助 Vasya 的老师,找到两个数字 - Vasya 可能获胜的最佳位置和最差位置。请注意,总成绩表按照两次旅行的积分总和对参与者进行排序(第一名是获得最多积分的参与者)。如果两个或更多参与者获得相同的分数,则由评审团根据他们的选择为他们分配名额。保证每位奥运会参赛者都参加奥运会的两次巡回赛。

输入

第一行包含两个以空格分隔的整数 n, x (1 ≤ n ≤ 105; 0 ≤ x ≤ 2·105) — 奥林匹克参赛人数和 Vasya 获得的最低分数。

第二行包含 n 个空格分隔的整数:a1, a2, ..., an (0 ≤ ai ≤ 105) — 参与者在第一次游览中的积分。

第三行包含 n 个空格分隔的整数:b1, b2, ..., bn (0 ≤ bi ≤ 105) — 第二次旅行中参与者的积分。

参与者的分数以任意顺序给出。可以保证 Vasya 参加了奥林匹克竞赛 — 有两个整数 i, j (1 ≤ i, j ≤ n),使得 ai + bj ≥ x。

输出

打印两个以空格分隔的整数——Vasya 在奥林匹克竞赛中可能获得的最佳名次和最差名次。

示例

输入 #1

5 2
1 1 1 1 1
1 1 1 1 1

输出 #1

1 5

输入 #2

6 7
4 3 5 6 4 4
8 6 0 4 3 4

输出 #2

1 5

注意

在第一个文本样本中,无论如何,所有 5 名参与者每人都获得 2 分。根据评审团的决定,瓦西亚可以获得第一名(最好)和最后(最差)第五名。

在最好情况下的第二个测试样本中,Vasya 再次获胜:如果总成绩表如下所示,他可以赢得 12 分,成为绝对获胜者 - {4:8, 6:4, 3:6, 4:4, 4:3, 5:0}。

在这个表中,所有参与者按积分递减排序,我们可以看到参与者在第一次和第二次旅行中赚了多少钱。

在最坏的情况下,如果牌桌是这样的——{4:8, 4:6, 6:4, 5:4, 4:3, 3:0},瓦夏可以获得第五名,并且他在第一轮和第二轮比赛中分别获得 4 和 3 分。