يبني Farmer John حديقة جميلة ويحتاج لنقل كمية كبيرة من التراب.
الحديقة صف من $N$ أحواض زهور ($1 \le N \le 100$). الحوض $i$ فيه أولًا $A_{i}$ وحدات تراب ويريد تحويلها إلى $B_{i}$. جميع $A_{i}$ و$B_{i}$ أعداد صحيحة في $0..10$.
يمكنه شراء وحدة ووضعها في أي حوض بكلفة $X$، أو إزالة وحدة من أي حوض وشحنها بعيدًا بكلفة $Y$، أو نقل وحدة من $i$ إلى $j$ بكلفة $Z$ مضروبًا في $|i-j|$. احسب أقل كلفة كلية.
الإدخال
- السطر 1: أعداد صحيحة تفصلها مسافات $N$ و$X$ و$Y$ و$Z$؛ $0 \le X, Y, Z \le 1000$.
- الأسطر $2..1+N$: السطر $i+1$ يحتوي $A_{i}$ و$B_{i}$ بمسافة.
الإخراج
- السطر 1: عدد صحيح هو أقل كلفة للمشروع.
أمثلة
الإدخال 1
4 100 200 1
1 4
2 3
3 2
4 0الإخراج 1
210ملاحظة
أربعة أحواض في صف فيها 1 و2 و3 و4 وحدات، ويريد 4 و3 و2 و0. كلفة الإضافة والإزالة والنقل 100 و200 و1.
يجب إزالة وحدة من الحوض 4 بكلفة 200. الباقي ينقل بكلفة 10: ثلاث وحدات من 4 إلى 1 ووحدة من 3 إلى 2.
نسبة المسألة: Brian Dean, 2012