Подготовка к заключительному этапу всероссийской олимпиады школьников по информатике 3025 года идёт полным ходом. Уже готовы и набор задач, и разборы к ним. Единственное, что осталось сделать — настроить компьютеры, на которых участники будут писать олимпиаду. Но сперва устройства надо доставить к месту проведения.
Число участников заключительного этапа ВсОШ 3025 сильно увеличилось по сравнению с предыдущими годами, поэтому компьютеров необходимо много. Все они уже разложены по $$$n$$$ контейнерам, $$$i$$$-й из которых весит $$$w_i$$$ килограммов. Задачу доставки этих контейнеров поручили транспортной компании, у которой (по счастливой случайности) есть ровно $$$n$$$ машин, причём стоимость провоза одного килограмма груза на $$$j$$$-й из машин равна $$$p_j$$$ рублей. Таким образом, стоимость перевоза контейнера номер $$$i$$$ на машине номер $$$j$$$ равна $$$w_i \cdot p_j$$$ рублей. В одной машине можно перевозить только один контейнер!
Сейчас перед менеджерами транспортной компании стоит задача распределения контейнеров по машинам. Стоимость перевозки одного контейнера не должна превышать $$$k$$$ рублей (иначе перевозку сочтут неоптимальной), но при этом менеджеры хотят максимизировать суммарную стоимость перевозки всех контейнеров. Помогите им: найдите максимально возможную суммарную стоимость.
В первой строке вводятся числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 10^5, 1 \leq k \leq 10^{18}$$$) — количество контейнеров и машин, а также максимально возможная стоимость перевозки одного контейнера.
В следующей строке находятся $$$n$$$ чисел $$$w_1, w_2, \dots, w_n$$$ ($$$1 \leq w_i \leq 10^6$$$) — массы контейнеров.
В следующей строке находятся $$$n$$$ чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \leq p_j \leq 10^6$$$) — стоимости перевозки одного килограмма груза на каждой из машин.
Обратите внимание на то, что число $$$k$$$ и значение ответа в этой задаче могут превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Выведите одно число — максимально возможную суммарную стоимость перевозки всех контейнеров. Если подходящего способа распределить контейнеры по машинам не существует, выведите число «$$$-1$$$» (без кавычек).
Решения, правильно работающие при $$$n \leq 3$$$, будут оцениваться в $$$20$$$ баллов.
Решения, правильно работающие при $$$n \leq 7$$$, будут оцениваться в $$$40$$$ баллов.
Решения, правильно работающие при $$$n \leq 1000$$$, будут оцениваться в $$$60$$$ баллов.
Решения, правильно работающие, когда $$$w_1=w_2=\dots=w_n$$$, будут оцениваться в $$$20$$$ баллов.
5 10010 2 3 8 420 7 50 5 25
370
3 350200 100 3003 1 2
-1
В первом примере из условия максимальная стоимость перевозки будет равна $$$10 \times 7 + 2 \times 50 + 3 \times 20 + 8 \times 5 + 4 \times 25=370$$$.
Во втором примере из условия ограничение по стоимости перевозки одного контейнера равно 350. Поэтому контейнер массой 300 кг можно перевести только по цене 1 рубль за килограмм, а цена 3 рубля за килограмм допустима только для контейнера массой 100 кг. Тогда для контейнера массой 200 кг останется только машина со стоимостью перевозки 2 рубля за килограмм, и соблюсти условие ограничения стоимости перевозки каждого контейнера не получится.
