Rain
Пролетен Турнир по Информатика, 2010
Time Limit: 0.4s, Memory Limit: 64MiB
За София могат да се кажат много неща – град с богата история, столица на България, мястото, където се намират парламентът и президентството. Градът, също така, играе важна роля при създаването на декори за различни пост-апокалиптични филми и компютърни игри. Този й вид отчасти е в следствие на киселнните дъждове, които падат там.

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

За по-голяма яснота можем да перефразираме задачата по следния начин. Гледан от стаята, можем да си представим, че первазът е интервал с дължина W. За всяка точка с целочислени координати от него можем да дадем стойността на най-киселинната капка, която е паднала там по време на дъжда. Тоест това ще са W числа A1, A2, ..., AW, включително, като по-малки числа означават по-малка киселинност. Върху интервала имаме разположени N незастъпващи се подинтервала с дължини съответно L1, L2, ..., LN в този ред (саксиите).

Ели иска да избере възможно най-малкото число F – фактор на препарата, такова, че съществува позициониране на саксиите при което в не повече от K от тях (включително краищата) попада капка с киселинност по-голяма от F. Ели не може да изхвърля саксии – тоест трябва да намери място на всяка една от тях.
Вход
На първия ред на стандартния вход ще бъдат зададени числата N, W и K – съответно броят саксии, дължината на перваза и максималният брой саксии, които Ели би пожертвала. На следващия ред ще има N цели числа L1, L2, ..., LN – дължината на саксиите в реда в който са наредени на перваза отляво надясно. На третия ред ще има W цели числа A1, A2, ..., AW – киселинността на най-киселинната капка, паднала по време на дъжда за всяка целочислена точка от перваза отляво надясно.
Изход
На стандартния изход изведете едно цяло число F – минималният фактор на защита, за който съществува отместване на саксиите при което в не повече от К от тях падат капки с киселинност по-голяма от F.
Ограничения
  • 1 ≤ N, W ≤ 100,000
  • 0 ≤ К ≤ 20
  • 1 ≤ Li ≤ 100,000
  • 0 ≤ Ai ≤ 100,000
  • L1 + L2 + ... + LNW
Примерен Вход Примерен Изход
4 15 1 2 3 2 4 4 4 3 4 9 2 3 8 0 2 7 1 1 0 5 5
Имаме 4 саксии с дължини съответно 2, 3, 2 и 4, перваз с дължина 15 и ограничение не повече от 1 саксия да бъде съсипана от дъжда. Някои от възможните разположения на саксиите по перваза са:
4 4 3 4 9 2 3 8 0 2 7 1 1 0 5
. └ ┘ . └ ─ ┘ . └ ┘ . └ ─ ─ ┘
или пък
└ ┘ └ ─ ┘ . . . └ ┘ . └ ─ ─ ┘
Забележете, че разположенията:
└ ─ ─ ┘ . . └ ┘ └ ┘ . └ ─ ┘ .
и
└ ┘ . └ ─ ─ ┘ . └ ┘ . └ ─ ┘ .
които биха постигнали по-добър отговор, са невалидни, тъй като сме разменили някои от саксиите.
Мрън!