bleach

Bleach

== include(page="template/taskheader" task_id="bleach") ==

Poveste şi cerinţă...

Aflat in societatea sufletelor, Ichigo afla ca are de invins $N$ inamici fiecare avand o putere cunoscuta. Dar desigur orice lupta are nevoie si de un plan. Ichigo a analizat toti inamicii si a descoperit $2$ lucruri despre ei:
 
* Inamicii s-au aliniat in ordine de la cel mai slab pana la cel mai puternic (de la cel cu puterea cea mai mica pana la cel cu puterea cea mai mare). Totusi cu o noapte in urma inamicii au avut o petrecere si derutati ei si-au schimbat pozitiile dar nu cu mai mult de $K$ de cea initiala (diferenta in modul intre pozitia initiala si cea finala sa fie maxim $K$).
 
* Ichigo a aflat deasemenea ca daca se lupta cu un inamic care are puterea $P$, atunci el in momentul respectiv trebuie sa aiba cel putin puterea $P$ ca sa il poata invinge (in cazul in care ambii au puterea $P$, Ichigo castiga deoarece e personajul principal). Deasemenea in momentul in care Ichigo invinge un inamic care are puterea $P$ atunci puterea lui va creste cu $P$ (practic ii absoarbe puterea inamicului).
 
Ichigo trebuie sa afle puterea minima cu care poate porni astfel incat sa ii poata invinge pe toti inamicii stiind ca el se poate lupta cu ei in orice ordine vrea. Deoarece el nu este informatician el va roaga pe voi sa il ajutati.

h2. Date de intrare

Fişierul de intrare $bleach.in$ ...

Fişierul de intrare $bleach.in$ va contine pee prima linie $2$ numere $N$ si $K$ cu semnificatia din enunt. Pe a doua linie se afla $N$ numere reprezentand puterile celor $N$ inamici. Al $i$-ulea numar reprezinta puterea inamicului care se afla pe pozitia $i$ dupa petrecere.

h2. Date de ieşire

În fişierul de ieşire $bleach.out$ ...

Fisierul de ieşire $bleach.out$ va contine un singur numar ce reprezinta puterea minima cu care trebuie sa porneasca Ichigo in lupta.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 1.000.000$
* $1 ≤ K ≤ 1000$
* puterea unui inamic se va incadra in intervalul $[1, 1.000.000.000]$
* Pentru $20%$ din teste $N ≤ 1000$
* Pentru alte $20%$ din teste $N ≤ 100.000$
* Pentru alte $20%$ din teste $1 ≤ K ≤ 10$
 

h2. Exemplu
table(example). |_. bleach.in |_. bleach.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 3
1 5 2 3 4
| 1

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="bleach") ==