Բիթային AND և OR

Էդուարդը և Էլիզան սիրում են միասին հաղթահարել կամայական ինտելեկտուալ խաղ և այսօր նրանց առաջադրվել է հետևյալ խնդիրը.

Շրջանաձև կանգնած են n մարդիկ, որոնցից յուրաքանչյուրը ունի գիտելիքի աստիճան՝ : Դա նշանակում է, որ -ի ձախ մասում կանգնած է -ը, երբ i > 1, իսկ -ի ձախ մասում -ը, -ի աջ մասում կանգնած է -ը, երբ i < n, իսկ -ի աջ մասում կանգնած է -ը:

Էդուարդին և Էլիզային անհրաժեշտ է մարդկանց բաժանել k անընդհատ խմբերի այնպես, որ ամեն մարդ լինի ճիշտ մի խմբում, բոլոր մարդիկ մասնակցեն և այդ բաժանման հզորությունը լինի մաքսիմալ: Բաժանման հզորությունը հավասար է խմբերի հզորությունների բիթային AND-ին, իսկ խմբի հզորությունը հավասար է խմբում մարդկանց գիտելիքների աստիճանի բիթային OR-ին:

Էդուարդը և Էլիզան իրար շատ լավ են հասկանում և այս խնդիրը լուծեցին շատ արագ, հերթը ձերն է:

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

Առաջին տողում տրված են n-ը և k-ն: Երկրորդ տողում տրված են մարդկանց գիտելիքների աստիճանները (0 ≤ Ai < ):

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

Բաժանման առավելագույն հզորությունը:

Սահմանափակումներ

• Թեստերի առաջին խմբի համար 1 ≤ k ≤ n ≤ 1000։

• Թեստերի երկրորդ խմբի համար 1 ≤ k ≤ n ≤ 500 000։

Օրինակներ

Աղբյուրը. Մարզային 2020