Олимпиадный тренинг

Задача . E. Гардероб

Задача

Оля хочет заказать шкаф. В нем будет n ящиков высотой a₁, a₂, ..., a_n, стоящих друг на друге в некотором порядке. Таким образом, каждый ящик можно представить в виде вертикального отрезка длины a_i, и все отрезки вместе должны составить отрезок от 0 до $\text{[math]}$ без перекрытий.

Некоторые из ящики важные (в таком случае b_i = 1), остальные нет (тогда b_i = 0). Оля считает, что удобство шкафа равняется количеству важных ящиков таких, что их нижняя граница находится на высоте от l до r включительно.

По данной информации о высотах ящиков и их важности найдите максимально возможное удобство шкафа, если ящики можно переставлять местами произвольным образом.

Входные данные

В первой строке находятся три целых числа n, l и r (1 ≤ n ≤ 10 000, 0 ≤ l ≤ r ≤ 10 000) — количество ящиков, нижняя и верхняя границы отрезка, куда должен попасть важный ящик, чтобы быть учтенным при подсчете удобства шкафа.

Во второй строке находятся n целых чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10 000) — высоты ящиков. Гарантируется, что суммарная высота всех ящиков (т. е. высота шкафа) не превосходит 10 000: Оля не сможет достать до ящиков выше.

Во второй строке находятся n целых чисел b₁, b₂, ..., b_n (0 ≤ b_i ≤ 1), где b_i равно 1, если ящик номер i важный, и 0 иначе.

Выходные данные

Выведите одно целое число — максимально возможное удобство шкафа.

Примечание

В первом примере можно, например, сначала поставить неважный ящик высоты 2, затем важные ящики высотой 1, 3 и 2 в таком порядке, затем — оставшиеся неважные ящики. В таком случае удобство равно 2, потому что нижние края важных ящиков размера 3 и 2 попадают в отрезок [3, 6].

Во втором примере нужно обязательно поставить невысокий ящик под высокий.

Примеры

№	Входные данные	Выходные данные
1	5 3 6 3 2 5 1 2 1 1 0 1 0	2
2	2 2 5 3 6 1 1	1

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	4

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет