У фермера Джона есть n коров разных размеров. Первоначально он построил для каждой коровы индивидуальный хлев, но теперь некоторые коровы переросли свои хлевы. В частности, первоначально ФД построила n коровников размером t[1]
, t[2]
, ..., t[n]
, в то время как коровы теперь имеют размер s[1]
, s[2]
,..., s[n]
(1 ≤ s[i]
, t[i]
≤ 10^9
).
Каждую ночь коровы проходят ритуал поиска хлева, чтобы спать. Корова i может спать в хлеву j тогда и только тогда, когда она помещаются в хлев (s[i]
≤ t[j]
). В каждом коровнике можно разместить не более одной коровы.
Будем говорить, что сопоставление коров с коровниками является максимальным тогда и только тогда, когда каждая корова, которой назначено стойло, может в нем поместиться, а каждая корова, которой не назначено стойло, не может поместиться ни в одном из пустых коровников.
Вычислить максимальное количество сопоставлений по модулю 10^9
+ 7.
Первая строка содержит число n (1 ≤ n ≤ 3000). Вторая строка содержит n целых чисел s[1]
, s[2]
,..., s[n]
. Третья строка содержит n целых чисел t[1]
, t[2]
, ..., t[n]
.
Выведите максимальное количество сопоставлений по модулю 10^9
+ 7.
Вот список всех девяти максимальных соответствий. Упорядоченная пара (i, j) означает, что корове i назначен коровник j.