Мангасын Тоглоом II

2s

512MB

1763

0%

Advanced Techniques

$n$ шаттай тоглоом тоглож байна. Шат бүрт нэг мангас байна. $1,2,\dots,n-1$ -р шат дээр мангасыг алах эсвэл орхих боломжтой. Харин $n$ -р шатанд тоглоомдоо ялахын тулд сүүлчийн мангасыг заавал алах ёстой.

Мангас алахад $sf$ хугацаа шаардана; $s$ нь мангасын хүч, $f$ нь таны ур чадварын коэффициент. Мангас алсны дараа шинэ коэффициент авна (коэффициент бага байх тусам сайн). Тоглоомд ялахад шаардагдах хамгийн бага нийт хугацааг ол.

Эх сурвалж: cses.fi

Оролтын формат

Эхний мөрөнд хоёр бүхэл тоо $n$ ба $x$ : шатуудын тоо ба ур чадварын анхны коэффициент.

Хоёр дахь мөрөнд $n$ бүхэл тоо $s_1,s_2,\dots,s_n$ : мангас бүрийн хүч.

Гурав дахь мөрөнд $n$ бүхэл тоо $f_1,f_2,\dots,f_n$ : мангас алсны дараах шинэ коэффициент.

Гаралтын формат

Нэг бүхэл тоо хэвлэ: тоглоомд ялах хамгийн бага нийт хугацаа.

Хязгаарлалт

$1 \le n \le 2 \cdot 10^5$
$1 \le x \le 10^6$
$1 \le s_i, f_i \le 10^6$

Жишээ

Оролт1

5 100
50 20 30 90 30
60 20 20 10 90

Гаралт1

0.1 / 64 KiB

Редактор уншиж байна...