תיאור הבעיה

אתם משחקים יחד עם 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