Лимак бол том цагаан баавгай. Тэр алгоримтын тэмцээнд $n$ ширхэг бодлого бэлджээ. $i$ дэх бодлого анхлан $p_{i}$ оноотой байна. Мөн шалгагчийн хэлснээр $i$ дэх бодлогыг бодоход $t_{i}$ минут зарцуулах аж. Бодлогууд хүндрэлийн түвшнээрээ эрэмбэлэгдээгүй ба магадгүй хүндэвтэр бодлогууд эхэндээ харьцангуй бага оноотой ч байж болно. Лимак анхдагч оноогоо аль эрт зарлачихсан тул өөрчлөхөд нэгэнт оройтсон байв. Гэсэн ч бодлогууд оноо алдах хурд буюу $c$-г тохируулах боломжтой хэвээр.

Бүх бодлогыг бодоход шаардлагатай хугацааг $T$ гэе. (ө.х $T = t_{1} + t_{2} + ... + t_{n}$). Тэмцээн $T$ үргэлжилнэ. Иймд бүх бодлогоо амжиж бодох боломжтой.

Бодлого бодоход өгөх оноо нь шугаман байдлаар буурна. $i$-р бодлогыг тэмцээн эхэлснээс хойш $x$ минутанд бодвол яг оноо авна. Энд нь Лимакийн сонгох бодит тоо.

$c$ тоог бэхлэгдсэн гэж үзье. Тэмцээний үеэр оролцогч бодлогуудаа ямар дарааллаар бодохоо шийднэ. Нийт $n!$ боломжит дараалал байх ба тус бүрдээ ямар нэгэн оноо өгнө. (бүхэл байх албагүй) Хамгийн өндөр оноо өгөх дарааллыг оптимал гэнэ. Өөрөөр хэлбэл энэ дарааллаас авах оноо өөр ямар ч дарааллаас хүртэх онооноос багагүй байна. Ядаж нэг оптимал дараалал байх нь ойлгомжтой. Харин нэгээс олон байх боломжтой.

Оролцогч тэмцээний эхэнд $t_{i}$ цагаа зөв тооцож оптимал дараалал сонгоно, мөн шалгагчид ч бодлогууд бодогдох хугацааг зөв таамагласан гэж үзэж буй.

$p_{i} < p_{j}$ байх ялгаатай $i$, $j$ бодлогуудын хувьд оролцогч $i$ бодлого дээр $j$-ээс өндөр авахад Лимак таагүй хандах ба ийм нөхцөл байдлыг тэрээр парадокс гэж нэрлэжээ.

$c = 0$ тохиолдолд ямар ч парадокс үүсэхгүй нь ойлгомжтой. Харин том $c$-н хувьд нөхцөл байдал арай ээдрээтэй. Ямар ч паракдокс үл үүсэх хамгийн их $c$-г ( болохыг санаарай) олно уу, өөрөөр хэлбэл ямар ч оптимал дарааллын хувьд нэг ч парадокс оршихгүй байх хамгийн их $c$-г тогтооно уу.

Нөхцөлийг хангах $c$ үргэлжид оршин байхыг баталж болно.

Оролт

Эхний мөрөнд бодлогуудын тоог илтгэх $n$ ($2 \le n \le 150 000$) тоо өгөгдөнө.

Хоёр дах мөрөнд $n$ ширхэг анхдагч оноонууд өгөгдөнө: $p_{1}, p_{2}, ..., p_{n}$ ($1 \le p_{i} \le 10^{8}$).

Гурав дах мөрөнд $n$ ширхэг $t_{1}, t_{2}, ..., t_{n}$ ($1 \le t_{i} \le 10^{8}$) тоонууд өгөгдөх ба $t_{i}$ нь $i$-р бодлогыг бодоход шаардагдах хугацааг илэрхийлнэ.

Гаралт

$c$-н хамгийн их утга болох бодит тоог хэвлэ. and there is no optimal order with a paradox.

Зөрүү нь $10^{ - 6}$ дотор байвал хариуг зөвд тооцно.

Хэрэв таны хариу $a$, зохиогчийн хариу $b$ байвал дараах нөхцөлд л шалгах програм таны хариуг зөвд тооцно:.

Эхний жишээнд $3$ бодлого өгөгдөнө. Эхнийх нь $(4, 1)$ (анхдагч оноо $4$ ба бодоход $1$ минут шаардана), хоёр дах бодлого $(3, 1)$ ба гурав дах бодлого $(10, 8)$. Нийт хугацаа $T = 1 + 1 + 8 = 10$.

$c = 0.7$ үед парадокс үүсэхийг харуулъя. $1$, $2$, $3$ дарааллаар бодох нь хамгийн их оноог өгнө:

1. Эхэлснээс хойш $1$ минутын дараа бодно:
2. Эхэлснээс хойш $2$ минутын дараа бодно:
3. Эхэлснээс хойш $10$ минутын дараа бодно:

Иймд энэ дараалал $3.72 + 2.58 + 3 = 9.3$ оноо өгөх (Нөгөө $5$ боломжит дарааллыг шалгаж болох ба үүнээс бага оноо өгнө) ба $1$, $3$ бодлогуудын хувьд парадокс үүснэ. $4 < 10$ боловч $3.72 > 3$ байх тул парадокс юм. Цаашилбал $c = 0.625$ тохиолдолд ямар ч парадокс үл үүсэх ба үүнээс $c$ бүрийн хувьд парадокс үүсэх юм.

Хоёр дах жишээнд $24$ дараалал бүгд оптимал.

Гурав дах жишээнд $c = 1$ байхад ч парадокс үүсэхгүй.