وصف المسألة

أنت تلعب مع J-كون باستخدام لعبة أميداكوجي (قرعة السلم). تتكون أميداكوجي من $n$ من الأعمدة الرأسية و $m$ من القضبان الأفقية. تُرقّم الأعمدة الرأسية من $1$ إلى $n$ بالترتيب من اليسار إلى اليمين، وفي الطرف السفلي للعمود الرأسي $i$ كُتب عدد صحيح موجب $s_i$.

الشكل 3-1: مثال على أميداكوجي ($n = 4, m = 5, s_1 = 20, s_2 = 80, s_3 = 100, s_4 = 50$)

عند تتبع المسار بالترتيب من أعلى نقطة في العمود الرأسي $i$، فإن العدد الصحيح المكتوب عند الطرف السفلي الذي يتم الوصول إليه هو النتيجة عند اختيار العمود الرأسي $i$. على سبيل المثال، في الشكل 3-1، اختيار العمود الرأسي $1$ يعطي $80$ نقطة، واختيار العمود الرأسي $2$ يعطي $100$ نقطة.

الشكل 3-2: مثال على كيفية تتبع المسارات

قرر J-كون اختيار $k$ من الأعمدة الرأسية المتتالية من العمود الرأسي $1$ إلى العمود الرأسي $k$. مجموع النقاط عند اختيار تلك الأعمدة الرأسية الـ $k$ هو نتيجة J-كون. ومع ذلك، يمكنك اختيار قضيب أفقي واحد في أميداكوجي وحذفه من أميداكوجي (أو يمكنك عدم حذف أي قضيب أفقي). إذا قمت بحذف قضيب أفقي واحد، فستكون نتيجة J-كون هي مجموع النقاط عند اختيار الأعمدة الرأسية الـ $k$ المتتالية من العمود الرأسي $1$ إلى العمود الرأسي $k$ في أميداكوجي بعد الحذف.

بمعلومية شكل أميداكوجي وعدد الأعمدة الرأسية $k$ التي يختارها J-كون كإدخال، اكتب برنامجًا لإيجاد أصغر قيمة ممكنة لنتيجة J-كون.

الإدخال

• السطر $1$ يحتوي على $4$ أعداد صحيحة $n, m, h, k$ مفصولة بمسافات. يمثل $n$ ($2 \le n \le 1000$) عدد الأعمدة الرأسية، ويمثل $m$ ($1 \le m \le 100000$) عدد القضبان الأفقية، ويمثل $h$ ($2 \le h \le 1000$) طول الأعمدة الرأسية، ويمثل $k$ ($1 \le k \le n$) عدد الأعمدة الرأسية التي يختارها J-كون.
• الأسطر الـ $n$ التالية تحتوي على النقاط المكتوبة عند الأطراف السفلية للأعمدة الرأسية. السطر $(i + 1)$ ($1 \le i \le n$) يحتوي على عدد صحيح موجب $s_i$. كما يتحقق $s_1 + s_2 + \cdots + s_n \le 2000000000 = 2 \times 10^9$.
• الأسطر الـ $m$ التالية تحتوي على مواقع القضبان الأفقية. تُرقّم القضبان الأفقية من $1$ إلى $m$. السطر $(i + n + 1)$ ($1 \le i \le m$) يحتوي على $2$ من الأعداد الصحيحة $a_i, b_i$ ($1 \le a_i \le n - 1, 1 \le b_i \le h - 1$) مفصولين بمسافة يمثلان موقع القضيب الأفقي $i$: يربط القضيب الأفقي $i$ بين العمود الرأسي $a_i$ والعمود الرأسي $a_i + 1$، وتكون مسافته من الطرف العلوي هي $b_i$. لا يشترك أي $2$ من القضبان الأفقية في نقطة طرفية.

من بين بيانات الاختبار، في $20\%$ من الدرجات تكون نتيجة J-كون أصغر ما يمكن عند عدم حذف أي قضيب أفقي. كما أن $30\%$ من الدرجات تحقق $n \le 20, m \le 30, h \le 10$، و $60\%$ من الدرجات تحقق $m \le 1000$.

الإخراج

اطبع سطرًا واحدًا ($1$) يحتوي فقط على أصغر قيمة ممكنة لنتيجة J-كون.

Sample 1

4 5 7 2
20
80
100
50
1 1
2 6
2 3
1 5
3 1

100

Sample 2

2 2 5 1
10
20
1 1
1 3

10

شرح الأمثلة

المثال 1 يقابل الشكل 3-1، وتكون نتيجة J-كون أصغر ما يمكن عندما تحذف القضيب الأفقي $4$ (القضيب الأفقي الذي يربط العمود الرأسي $1$ والعمود الرأسي $2$ على مسافة $5$ من الطرف العلوي). في المثال 2، تكون نتيجة J-كون أصغر ما يمكن عندما لا تحذف أي قضيب أفقي (انظر الشكل 3-3).

الشكل 3-3