Посреди Великого озера расположился примечательный остров Фишланд. Дима очень любит рыбачить на этом острове. Чтобы улов был большим, он установил $$$n$$$ удочек на берегу и провёл к каждой из них тропинку от центра острова. Для каждой удочки известно время, которое требуется, чтобы дойти до неё от центра острова или обратно.
Фишланд — особенный остров, поэтому через каждую минуту ровно на одну из удочек клюёт. Если в этот момент Дима находится возле этой удочки, то он вылавливает рыбу, а иначе она уплывает.
В одну из своих рыбалок Дима собрал информацию, на какую удочку клевало в каждый момент времени. Он хочет выяснить, какое максимальное количество рыб он смог бы поймать, если бы действовал оптимально. Помогите Диме это определить.
В начале рыбалки (в момент времени ноль) Дима находится в центре острова. Перемещаться между удочками он может только по тропинкам через центр. Вытаскивание рыбы из воды выполняется мгновенно.
Первая строка содержит одно натуральное число $$$1 \leq t \leq 10^5$$$ — количество минут, которое длилась рыбалка.
Вторая строка содержит одно натуральное число $$$1 \leq n \leq 10^5$$$ — количество расставленных удочек.
Следующие $$$t$$$ строк содержат по одному числу $$$a_i$$$ ($$$1 \leq a_i \leq n$$$) — номера удочек, на которые клевало в моменты времени 1, 2, 3, ..., $$$t$$$.
Последние $$$n$$$ строк содержат по одному числу $$$d_j$$$ ($$$1 \leq d_j \leq t$$$) — за сколько минут можно добраться от центра острова до удочек с номерами 1, 2, 3, ..., $$$n$$$.
Необходимо вывести одно число — максимальное количество рыб, которое мог бы выловить Дима.
Оценивание в задаче потестовое. Задача проверяется на всех тестах. Тесты разбиты на группы, соответствующие приведённым ниже подзадачам. Для каждой подзадачи указан максимальный балл, который можно получить в случае прохождения всех тестов, соответствующих этой подзадаче. Возможно получение частичных баллов за подзадачу.
Подзадача 1 (10 баллов): $$$n=1$$$.
Подзадача 2 (20 баллов): $$$n=2$$$.
Подзадача 3 (20 баллов): $$$n, t \leq 100$$$.
Подзадача 4 (20 баллов): все $$$d_j=1$$$.
Подзадача 5 (30 баллов): нет дополнительных ограничений.
221211
1
63332321123
2
Пояснение к примеру
В первом примере, куда бы ни пошёл Дима, удастся выловить только одну рыбу. Например, за одну минуту он может дойти до первой удочки как раз к моменту, когда на неё клюнет. Но после этого дойти до другой удочки он уже не успеет, так как на неё клюнет в момент времени 2, то есть уже через минуту, а идти до неё — две минуты.
Во втором примере Диме выгодно с самого начала пойти ко второй удочке и ловить рыбу, находясь у неё до конца рыбалки.
