علی تصمیم می‌گیرد به یک فرودگاه صحرایی رفته از کشور خارج شود برای این کار او از مکان یک خرمافروشی که به اندازه‌ی نامحدودی خرما دارد و در نقطه‌ی $(0,0)$ از نقشه‌ی او قرار دارد شروع کند و می‌خواهد به فرودگاه صحرایی که در نقطه‌ی $(a,b)$ است برسد. می‌داند که $N$‌ چاه آب در نقاط $(x_1,y_1)$ تا $(x_N,y_N)$ از کویر قرار دارند. در ضمن او به ازای هر یک متر حرکت $w$ گرم آب و $d$‌گرم خرما -در طول حرکت- مصرف می‌کند و ماشینی با گنجایش $k$‌ گرم بار -به جز وزن خود او- دارد اما فقط می‌تواند در جهت شمال، جنوب، شرق و غرب حرکت کند! او می‌خواهد با خریدن کم‌ترین میزان خرما در ابتدای مسیر به فرودگاه برسد.

در خط اول فایل ورودی به ترتیب $N$، $a$، $b$، $w$، $d$ و $k$ نوشته شده‌اند، در $N$‌ خط بعدی در هر خط یک $x_i$ و $y_i$ متناظر نوشته شده‌اند. ($1\leq N \leq 10^4$ و $0\leq a,b,w,d,k \leq 10^7$ و $-10^7 \leq x_i,y_i \leq 10^7$)

در یک خط کم‌ترین وزن خرما (به گرم) که علی باید بخرد را بنویسید.

• سوال بعد
• سوال قبل