Կարենը սիրում է ժամանակ առ ժամանակ համալսարանից հետո տուն գնալ ոտքով, և այսօր այդ օրերից մեկն է: Համալսարանը գտնվում է կոորդինատային ուղղի 0 կոորդինատով կետում, իսկ Կարենի տունը՝ L կոորդինատով կետում։ Կարենը չի գնում 0 կետից ձախ և իր տնից աջ, այսինքն քայլում է միայն [0, L] հատվածում: Նա սկսում է իր ճանապարհորոդությունը ամբողջ կոորդինատով կետից, կարող է շարժվել միայն աջ կամ ձախ և կարող է փոխել իր ուղղությունը միայն ամբողջ կոորդինատով կետերում։ Ինչպես բոլորս գիտենք՝ Հարրի Փոթերը հայտնի հրաշագործ է և փորձում է ամեն գնով հաղթել Վոլդեմորտին: [1, L]հատվածի ամբողջ կոորդինատով կետերում կան հորքրուքսներ, որոնք Հարրին ցանկանում է ձեռք բերել՝ Վոլդեմորտին հաղթելու համար: X կոորդինատով կետում կա հատ հորքրուքս, բայց կան նաև անպետք իրեր։ Հարրին ցանկանում է Կարենի օգնությամբ հավաքել որոշ հորքրուքսներ, իսկ մնացած հորքրուքսները հավաքել ինքնուրույն: Քանի որ Հարրին հրաշագործ է, նա կարող է Կարենին ուղարկել [0, L] հատվածի կամայական ամբողջ կոորդինատով կետ, իսկ հետո նաև ղեկավարել Կարենի շարժը: Երբ Կարենը անցնում է X – 0.5 (որտեղ X-ը ամբողջ թիվ է) կոորդինատով կետով, Կարենի մոտ ավելանում է Xկոորդինատով կետում գտնվող իր։ Եթե X կոորդինատով կետում դեռ կա հորքրուքս, ապա Կարենի մոտ հայտնվում է այդ հորքրուքսը։ Հակառակ դեպքում՝ անպետք իր: Ճանապարհորդության ավարտին Հարրին վերցնում է Կարենի հավաքած բոլոր իրերը։ Հարրին այժմ ցանկանում է իմանալ, թե նվազագույնը ինչքան էներգիա նա պետք է ծախսի, որպեսզի Կարենի մոտից իրարը վերցնելուց հետո նա ունենա բոլոր հորքրուքսնեը, և չունենա անպետք իրեր: Կարնեի մոտից իրերը վերցնելուց հետո Հարրին կարող է օգտագրծել հետևյալ 2 կախարդանքներից յուրաքանչյուրը ինչքան ցանկանա, սակայն ամեն անգամ որևէ կախարդանք օգտագործելը նրանից տանում է 1 էներգիա.
Նա կարող է վերացնել անպետք իր
Նա կորող է իր մոտ բերել Կարենի չհավաքած հորքրուքսներից որևէ մեկը։
Հարրին՝ իմանալով, որ Դուք քաղաքի ամենալավ ծրագրավորողն եք, խնդրում է Ձեզ օգնել իրեն հասկանալ, թե նվազագույնը ինչքան էներգիա նա պետք է ծախսի, որպեսզի ունենա բոլոր հորքրուքսները և ոչ մի ավելորդ իր:
Մուտքային տվյալներ
Տրված են Lը (1 ≤ L ≤ 2 ·) և L հատ թիվ, որտեղ - ն (1 ≤ i ≤ L)i կոորդինատով կետում հորքրուքսների քանակն է (0 ≤≤):
Ելքային տվյալներ
Պետք է արտածել, թե նվազագույնը ինչքան էներգիա պետք է ծախսի Հարրին՝ իր նպատակին հասնելու համար: