Order Splitter
Электронная биржа — это сложная система, которая обрабатывает заказы в реальном времени. В современном мире такие биржи ежедневно обрабатывают миллионы заказов. Вы основали небольшую компанию, предоставляющую услуги исполнения заказов для клиентов, и столкнулись с задачей распределения крупного заказа между несколькими биржами. Создание новой биржи — это конкурентный процесс, поэтому для распределения заказа доступно лишь ограниченное количество бирж: 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, выведите меньшее значение.