Розділювач Замовлень
Електронна біржа — це складна система обробки замовлень у режимі реального часу. Сьогодні електронні біржі працюють на ринку, обробляючи мільйони замовлень щодня. Ви заснували невелику компанію, яка надає послуги виконання для клієнтів, і стикаєтеся з проблемою розподілу великих замовлень між біржами. Оскільки створення нової біржі є дуже конкурентним, існує лише обмежена кількість бірж, доступних для розподілу замовлення 1 ≤ N ≤ 30.
Замовлення має номінал (загальну суму, яку потрібно виконати на біржах) 1 ≤ L ≤ 10^9 та ціну. У цій задачі вас цікавить лише номінал. Ціна, за якою замовлення надсилається на біржу, буде надана клієнтом і передана на біржу без змін. Це замовлення має бути розділене на кілька дочірніх замовлень, які надсилаються на біржу, відповідно до заданих коефіцієнтів R_i для кожного 0 ≤ i < N. Однак кожна біржа має обмеження на розмір кроку. Кожен номінал замовлення має бути кратним певному розміру кроку, визначеному біржею. Вам надано розмір кроку кожної біржі S_i, що означає, що кожна біржа може приймати лише замовлення номіналом S_i, 2·S_i, 3·S_i...
Оскільки не завжди можливо точно розділити номінал замовлення клієнта на дочірні замовлення, має бути написаний алгоритм для досягнення найкращого можливого розподілу, який мінімізує D=|L-C_i|, де номінали дочірніх замовлень, розподілених на відповідні біржі, позначені як C_i. Клієнти віддають перевагу, щоб розмір дочірнього замовлення не сильно відрізнявся від CR_i=L·R_i/R_i. Щоб задовольнити цю вимогу, C_i може бути отримано лише шляхом округлення CR_i вгору або вниз до розміру кроку. Однак, якщо CR_i ділиться на S_i, вимагається, щоб C_i = CR_i. Це означає, що ви повинні надіслати номінал дочірнього замовлення відповідно до заданого коефіцієнта, якщо це можливо, або в іншому випадку округлити його вгору або вниз. Якщо округлення вниз дає номінал 0, тоді ви можете не надсилати замовлення на біржу.
Вхідні дані
Перша строка кожного тестового випадку містить 2 цілі числа: кількість бірж 1 ≤ N ≤ 30, номінал замовлення для розподілу 1 ≤ L ≤ 10^9. Друга строка містить N цілих чисел, що визначають 0 ≤ R_i ≤ 100, R_i > 0. Третя строка містить N цілих чисел, що визначають розміри кроків 1 ≤ S_i ≤ 10^9.
Вихідні дані
Для кожного тестового випадку виведіть один рядок, що містить сумарний номінал дочірніх замовлень L_r=C_i, оптимізований відповідно до описаних правил. Якщо існує більше ніж одне оптимальне значення L_r, виведіть менше значення.