За София могат да се кажат много неща – град с богата история, столица на България, мястото, където се намират парламентът и президентството. Градът, също така, играе важна роля при създаването на декори за различни пост-апокалиптични филми и компютърни игри. Този й вид отчасти е в следствие на киселнните дъждове, които падат там.

В един такъв дъждовен ден, Ели е притеснена за саксиите с цветя на перваза на прозореца си. Дъждът пада в тях, и докато някои от капките са съвсем обикновени, други са киселинни. Елеонора е решила да предпази цветята като сипе в тях препарат, който помага на почвата да неутрализира капки с до определено ниво на киселинност. Различните препарати са с различна цена, като тези, които предпазват по-силно, са съответно по-скъпи. Също така тя може да мести саксиите наляво и надясно по перваза, но без да разменя местата им. Разбира се, две саксии не могат да се застъпват. Ели решава да вземе възможно най-евтиния препарат, който й позволява да нареди саксиите по такъв начин, че в не повече от няколко от тях да паднат капки с по-голяма киселинност отколкото предпазва препарата. Помогнете й като определите най-малкото число като защитен фактор на препарата, което позволява това.

За по-голяма яснота можем да перефразираме задачата по следния начин. Гледан от стаята, можем да си представим, че первазът е интервал с дължина W. За всяка точка с целочислени координати от него можем да дадем стойността на най-киселинната капка, която е паднала там по време на дъжда. Тоест това ще са W числа A₁, A₂, ..., A_W, включително, като по-малки числа означават по-малка киселинност. Върху интервала имаме разположени N незастъпващи се подинтервала с дължини съответно L₁, L₂, ..., L_N в този ред (саксиите).

Ели иска да избере възможно най-малкото число F – фактор на препарата, такова, че съществува позициониране на саксиите при което в не повече от K от тях (включително краищата) попада капка с киселинност по-голяма от F. Ели не може да изхвърля саксии – тоест трябва да намери място на всяка една от тях. На първия ред на стандартния вход ще бъдат зададени числата N, W и K – съответно броят саксии, дължината на перваза и максималният брой саксии, които Ели би пожертвала. На следващия ред ще има N цели числа L₁, L₂, ..., L_N – дължината на саксиите в реда в който са наредени на перваза отляво надясно. На третия ред ще има W цели числа A₁, A₂, ..., A_W – киселинността на най-киселинната капка, паднала по време на дъжда за всяка целочислена точка от перваза отляво надясно. На стандартния изход изведете едно цяло число F – минималният фактор на защита, за който съществува отместване на саксиите при което в не повече от К от тях падат капки с киселинност по-голяма от F.

• 1 ≤ N, W ≤ 100,000
• 0 ≤ К ≤ 20
• 1 ≤ L_i ≤ 100,000
• 0 ≤ A_i ≤ 100,000
• L₁ + L₂ + ... + L_N ≤ W

Примерен Вход	Примерен Изход
4 15 1 2 3 2 4 4 4 3 4 9 2 3 8 0 2 7 1 1 0 5	5