| VK Cup 2018 - Раунд 2 |
|---|
| Закончено |
Оля хочет заказать шкаф. В нем будет n ящиков высотой a1, a2, ..., an, стоящих друг на друге в некотором порядке. Таким образом, каждый ящик можно представить в виде вертикального отрезка длины ai, и все отрезки вместе должны составить отрезок от 0 до 
без перекрытий.
Некоторые из ящики важные (в таком случае bi = 1), остальные нет (тогда bi = 0). Оля считает, что удобство шкафа равняется количеству важных ящиков таких, что их нижняя граница находится на высоте от l до r включительно.
По данной информации о высотах ящиков и их важности найдите максимально возможное удобство шкафа, если ящики можно переставлять местами произвольным образом.
В первой строке находятся три целых числа n, l и r (1 ≤ n ≤ 10 000, 0 ≤ l ≤ r ≤ 10 000) — количество ящиков, нижняя и верхняя границы отрезка, куда должен попасть важный ящик, чтобы быть учтенным при подсчете удобства шкафа.
Во второй строке находятся n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 10 000) — высоты ящиков. Гарантируется, что суммарная высота всех ящиков (т. е. высота шкафа) не превосходит 10 000: Оля не сможет достать до ящиков выше.
Во второй строке находятся n целых чисел b1, b2, ..., bn (0 ≤ bi ≤ 1), где bi равно 1, если ящик номер i важный, и 0 иначе.
Выведите одно целое число — максимально возможное удобство шкафа.
5 3 6
3 2 5 1 2
1 1 0 1 0
2
2 2 5
3 6
1 1
1
В первом примере можно, например, сначала поставить неважный ящик высоты 2, затем важные ящики высотой 1, 3 и 2 в таком порядке, затем — оставшиеся неважные ящики. В таком случае удобство равно 2, потому что нижние края важных ящиков размера 3 и 2 попадают в отрезок [3, 6].
Во втором примере нужно обязательно поставить невысокий ящик под высокий.
