Успішно склавши сесію, Петрик збирається відправитись автівкою до своїх батьків у Кременчук, відстань до якого від університету рівна $d$ кілометрів. 

Машина Петрика не є новою, тому споживає цілих $w$ літрів бензину кожен кілометр дороги. По дорозі до рідної домівки розміщено $n$ заправок, кожна з яких пропонує пальне за $c_i$ гривень за літр та розміщена на відстані $x_i$ кілометрів від точки відправлення. Проте, на подив, кожна заправка пропонує свій унікальний вид бензину, які змішувати між собою в баку не можна. 

Перед поїздкою Петрик хоче замінити розмір бака для пального, проте не знає на який саме. Допоможіть Петрику визначити мінімальний розмір бака для пального такий, що вартість дороги до родичів буде мінімальною. Тобто першочергово слід мінімізувати затрати на пальне.

Гарантується, що початково бак пустий та існує таке $i$, що $x_i = 0$.