시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 3 2 2 66.667%

문제

Maričina baka ima veliki voćnjak i svakog jutra na tržnicu nosi šljive. Marica je jutros baki nabrala n košara šljiva, ali baka se još nije probudila zbog sinoćnjeg tulumarenja, pa se Marica želi još malo poigrati. Neke će šljive iz košara pojesti, a potom ubrati još šljiva iz voćnjaka.

Maričin je cilj da za svaki prirodan broj iz intervala [A, B] (uključivo) postoji barem jedna košara koja sadrži taj broj šljiva. Znajući trenutačni broj šljiva u svakoj košari, odredite minimalan broj operacija koje Marica mora učiniti da bi ostvarila svoj zadatak, ako je svaka od operacija jedno od sljedećeg:

  • pojedi šljivu iz neke košare,
  • uberi šljivu iz voćnjaka i stavi je u neku košaru.

입력

U prvom redu nalazi se prirodni broj n (n ≤ 5000) — broj košara. U sljedećem redu nalaze se prirodni brojevi A i B (1 ≤ A ≤ B ≤ 106 , B − A + 1 ≤ n) iz teksta zadatka. U i-tom od sljedećih n redova nalazi se cijeli broj ai (1 ≤ ai ≤ 106 ), broj šljiva u i-toj košari.

출력

U prvi i jedini red ispišite traženi minimalan broj operacija.

예제 입력 1

5
3 6
8
7
1
10
9

예제 출력 1

11

예제 입력 2

7
64 68
62
5
97
66
74
47
86

예제 출력 2

45

힌트