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

Задача . E. Краны с водой

Задача

Темы: Бинарный поиск жадные алгоритмы сортировки *2000

Рассмотрим систему из n кранов, наполняющих некоторую емкость водой. Кран i может быть настроен на подачу любого объема воды от 0 до a_i мл в секунду (это число может быть действительным). Вода в i-м кране имеет температуру t_i.

Если для каждого $\text{[math]}$ выставить, чтобы i-й кран наливал ровно x_i мл воды в секунду, то температура воды в результате будет $\text{[math]}$ (если $\text{[math]}$ , то во избежание деления на ноль считаем температуру равной 0).

Вам необходимо выставить все краны таким образом, чтобы полученная температура была ровно T. Какой максимальный объем воды в секунду температуры T можно получить?

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

В первой строке записаны два целых числа n и T (1 ≤ n ≤ 200000, 1 ≤ T ≤ 10⁶) — количество кранов с водой и желаемая температура воды соответственно.

Во второй строке записаны n целых чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁶), где a_i — максимальный объем воды, который i-й кран может выдавать в секунду.

В третьей строке записаны n целых чисел t₁, t₂, ..., t_n (1 ≤ t_i ≤ 10⁶) — температура воды в каждом кране.

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

Выведите максимальный возможный объем воды температуры T, который можно получить в секунду (если невозможно получить воду желаемой температуры, то ответ равен 0).

Ваш ответ будет засчитан, если его абсолютная или относительная ошибка не будет превосходить 10^- 6.

Примеры

№	Входные данные	Выходные данные
1	2 100 3 10 50 150	6.000000000000000
2	3 9 5 5 30 6 6 10	40.000000000000000
3	2 12 1 3 10 15	1.666666666666667

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

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

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

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

Ваш ответ

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

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

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

Нет