33210번 - Cetinska Cestogradnja 스페셜 저지다국어

문제

U pustinji se nalazi rijeka i dva grada koja leže na njenim krajevima. Rijeka je izlomljena linija koja počinje u jednom gradu i završava u drugom.

Svaki ravan segment rijeke teče strogo od juga prema sjeveru, odnosno u smjeru rastuće y koordinate.

Moramo izgraditi cestu koja će povezati ta dva grada. Cesta može ići uz rijeku, ali ju ne može jednostavno prijeći: most se mora izgraditi na svakom prijelazu.

Izgradnja jednog metra ceste na tlu košta 1ドル$ jedinicu, a izgradnja svakog mosta (prijelaza) košta $T$.

Unutar gradova promet je već riješen, tako da cesta može početi i završiti na bilo kojoj strani rijeke.

입력

U prvom retku nalaze se dva broja: prirodni broj $N$ (2ドル ≤ N ≤ 1500$), koji označava broj čvorišta rijeke (uključujući i gradove) i realni broj $T$ (0ドル < T ≤ 10^6$), koji označava cijenu jednog mosta. Broj $T$ imat će najviše dvije decimale.

U svakom od sljedećih $N$ redaka nalaze se po dva cijela broja $X_i$ i $Y_i$ ($|X_i |, |Y_i | ≤ 10^5 $).

Ovaj par označava koordinate $i$-tog čvorišta rijeke. Zadovoljavaju $Y_i < Y_{i+1},ドル 1ドル ≤ i < N$.

Ne postoje tri kolinearne točke u ulazu. Cesta mora početi u točki $(X_1, Y_1)$ i završiti u točki $(X_N , Y_N )$.

출력

Program mora ispisati jedan broj koji označava najmanju moguću cijenu projekta.

Odgovor će biti prihvaćen ako se razlikuje od točnog rješenja za najviše 10ドル^{-6}$.

제한

힌트

Pojašnjenje prvog probnog primjera: Pogledajte sliku.