Түрмеде \(n\) қылмыскер бар, олар \(1\)-ден \(n\)-ға дейін нөмірленген. Әрбір қылмыскердің \(i\)-ші күш \(a_i\) және \(b_i\) параметрі бар, ол топқа әрбір қосымша серіктес үшін оның күшінің өзгеруін көрсетеді. \(b_i\) параметрі оң немесе теріс болуы мүмкін.

Қылмыскерлерді топтарға бөлу керек, әр топ — бұл қылмыскерлердің үздіксіз бөлігі. Барлық қылмыскерлер топтарға кіруі керек.

Топтың күшін, оның ішіндегі қылмыскерлердің нөмірлері \(l\)-ден \(r\)-ге дейін болса, келесі формула бойынша есептейді: \[\text{groupPower}(l, r) = \max_{i=l}^{r} \left(a_i + b_i \cdot (r - l)\right),\]

Қылмыскерлерді топтарға бөлу керек, солайша барлық топтар арасында ең үлкен күштің мәнін минимизациялаңыз.

Енгізу

Бірінші жолда бір сан \(n\) \((1 \leq n \leq 10^5)\) — қылмыскерлердің саны көрсетіледі.

Екінші жолда \(n\) бүтін сан \(a_1, a_2, \dots, a_n\) \((-10^9 \leq a_i \leq 10^9)\) — қылмыскерлердің күштері.

Үшінші жолда \(n\) бүтін сан \(b_1, b_2, \dots, b_n\) \((-10^9 \leq b_i \leq 10^9)\) — әрбір серіктес үшін күштің модификаторлары.

Шығару

Бір санды шығарыңыз — қылмыскерлерді топтарға оптималды бөлу кезінде максималды топ күшінің минималды мүмкін мәні.

Бағалау жүйесі

Мысалдар

Енгізу 1

6
6 -3
-3 1
-6 -2
4 6
6 -3
-2 -2

Жауап 1

4

Ескертпелер

Тестілік мысалға арналған топтарға оңтайлы бөлу: \((1, 3)\), \((4, 4)\), \((5, 6)\).

Бұл бөлініс бойынша топтың максималды күші 4-ке тең. Бұл максималды күштің минималды мүмкін болатын мәні, және төмен нәтиже алу мүмкін емес.