Համացանց

Այոայ գեղեցիկ քաղաքում կա ընդհանուր առմամբ տուն, որոնք ուղիղ գծի երկայնքով։ -րդ տան բնակիչը ցանկանում է, որ իր տանը կապի արագությունը լինի առնվազն ։

Նորանշանակ քաղաքապետ Համլետը ցանկանում է նոր անտենաներ տեղադրել՝ ապահովելու համար կայուն ցանցային կապ քաղաքացիների համար։

Երբ տեղադրվում է հզորությամբ անտենա և հաջորդական տների համար, այն ապահովում է կապի արագություն ընտրված տների համար։ հաջորդական տների քանակը չպետք է գերազանցի -ը, և յուրաքանչյուր անտենայի համար այն կարող է տարբեր լինել։ Սակայն տեխնիկական սահմանափակումների պատճառով մեկ անտենայի առավելագույն հզորությունը չի կարող գերազանցել -ը։ Բացի այդ, ռադիո խափանումները կանխելու համար անտենաները պետք է տեղադրվեն այնպես, որ ոչ մի տուն կապ չստանա երկու տարբեր անտենաներից։

Քաղաքի բոլոր քաղաքացիներին բավարարելու համար Համլետը ցանկանում է ապահովել պահանջվող կապի արագությունը յուրաքանչյուր տանը։ Բացի այդ, քաղաքային բյուջեն խնայելու նպատակով նա ցանկանում է նվազեցնել տեղադրված անտենաների հզորությունների գումարը։ Օգնեք Համլետին գտնել տեղադրված անտենաների հզորությունների նվազագույն գումարը, որը կապահովի անհրաժեշտ կապի արագությունը բոլոր տների համար։

Մուտքային տվյալներ

Առաջին տողը պարունակում է երկու ամբողջ թիվ՝ և ՝ տների քանակը և մեկ անտենայի առավելագույն ուժգնությունը :

Երկրորդ տողը պարունակում է ամբողջ թիվ՝ ՝ յուրաքանչյուր տան պահանջվող կապի արագությունը ։

Ելքային տվյալներ

Տպեք տեղադրված անտենաների հզորությունների նվազագույն գումարը, որը կապահովի անհրաժեշտ կապի արագությունը բոլոր տների համար։

Oրինակներ

Մուտք	Ելք
7 5 2 4 3 3 1 4 5	19

Ենթախնդիրներ

Համար	Սահմանափակում	Միավոր
0	Օրինակը	0
1		15
2		20
3		15
4		25
5	Լրացուցիչ սահմանափակումներ չկան	25

Constraints

Time limit: 10 seconds

Memory limit: 512 MB

Output limit: 1 MB