print2160. Зубы дракона

printЗубы дракона

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Юный дракон еще не знает, что может просто похищать принцесс, если у него появляется такое желание. Поэтому он хочет понравиться юной принцессе, которая пока не намерена бояться драконов, особенно юных.
Дракон хоть был и юн, а зубов для устрашения всего живого выросло у него достаточно. А именно, у дракона было две челюсти, в каждой из которых был ряд ровно из `n` зубов. Челюсти были направлены друг на друга и напротив каждого из зубов находился зуб из противоположной челюсти.

28879.png

Природа сделала дракону подарок – все его зубы имели одинаковую ширину. Второго подарка она делать не стала и поэтому длины зубов у дракона могли различаться.
Чтобы понравиться принцессе, дракону не стоит показывать ей свои зубы вовсе. Однако, если существует хоть одна пара зубов, направленных друг на друга, суммарная длина которых превосходит `d` сантиметров, то челюсть не может закрыться, зубы станут видны невооруженным глазом, и, скорее всего, принцесса испугается драконьего вида. По этой причине дракону необходимо сдвинуть нижнюю челюсть на некоторое число зубов вбок (налево или направо).

28880.png

Двигать таким образом челюсть не очень приятно, и дракон интересуется, на какое наименьшее число зубов ему стоит сдвинуть челюсть для того, чтобы понравиться принцессе.
Первая строка входного файла содержит два числа `n` и `d` (`1\ ≤\ n\ ≤\ 1000`, `1\ ≤\ d\ ≤\ 10^9`). Во второй строке содержится `n` целых чисел `a_i` (`0\ ≤\ a_i\ ≤\ 10^9`) – длины зубов из верхнего ряда. В третьей строке в аналогичном формате заданы длины зубов из нижнего ряда.
В выходной файл выведите единственное число – наименьшее число зубов, на которое дракону следует подвинуть нижнюю челюсть. Если невозможно, то вывести `n`.

Пример ввода 1

4 4
2 1 3 2
2 1 3 1

Пример вывода 1

1

Пример ввода 2

4 1
2 1 3 2
2 1 3 1

Пример вывода 2

4
Источник: neerc.ifmo.ru/school
loading