Codeforces Round 137 (Div. 2) |
---|
Закончено |
Мальчик Вася участвовал в олимпиаде. Учитель мальчика знает, что Вася получил за оба тура олимпиады в сумме не меньше, чем x баллов. У учителя есть результаты первого тура и результаты второго тура олимпиады, но вот беда — в результатах указаны лишь баллы, без фамилий. Учителю необходимо знать, на что Вася может рассчитывать.
Помогите учителю Васи, найдите два числа — наилучшее и наихудшее место, которое мог занять Вася. Учтите, что в итоговой таблице участники сортируются по сумме баллов за оба тура (у участника на первом месте больше всего баллов). Если два (или более) участника получили одинаковое количество баллов, жюри может им назначить места по своему усмотрению. Гарантируется, что каждый участник олимпиады участвовал в обоих турах олимпиады.
В первой строке записаны через пробел два целых числа n, x (1 ≤ n ≤ 105; 0 ≤ x ≤ 2·105) — количество участников олимпиады и минимальное количество набранных Васей баллов.
Во второй строке записаны n целых чисел через пробел: a1, a2, ..., an (0 ≤ ai ≤ 105) — баллы участников в первом туре.
В третьей строке записаны n целых чисел через пробел: b1, b2, ..., bn (0 ≤ bi ≤ 105) — баллы участников во втором туре.
Баллы участников заданы в произвольном порядке. Гарантируется, что Вася присутствовал на олимпиаде — существуют два целых числа i, j (1 ≤ i, j ≤ n) такие, что ai + bj ≥ x.
Выведите через пробел два целых числа — наилучшее и наихудшее место из тех, что мог занять Вася на олимпиаде.
5 2
1 1 1 1 1
1 1 1 1 1
1 5
6 7
4 3 5 6 4 4
8 6 0 4 3 4
1 5
В первом тестовом примере в любом случае все 5 участников набирают по 2 балла. В зависимости от решения жюри, Васе могут присудить как первое (наилучшее) место, так и последнее (наихудшее), пятое.
Во втором тестовом примере в лучшем для Васи случае он снова выигрывает: он может набрать 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 балла соответственно.
Название |
---|