Բիթային AND և OR
Էդուարդը և Էլիզան սիրում են միասին հաղթահարել կամայական ինտելեկտուալ խաղ և այսօր նրանց առաջադրվել է հետևյալ խնդիրը.
Շրջանաձև կանգնած են n մարդիկ, որոնցից յուրաքանչյուրը ունի գիտելիքի աստիճան՝
i > 1, իսկ i < n, իսկ Էդուարդին և Էլիզային անհրաժեշտ է մարդկանց բաժանել
k անընդհատ խմբերի այնպես, որ ամեն մարդ լինի ճիշտ մի խմբում, բոլոր մարդիկ մասնակցեն և այդ բաժանման հզորությունը լինի մաքսիմալ: Բաժանման հզորությունը հավասար է խմբերի հզորությունների բիթային AND-ին, իսկ խմբի հզորությունը հավասար է խմբում մարդկանց գիտելիքների աստիճանի բիթային OR-ին:Էդուարդը և Էլիզան իրար շատ լավ են հասկանում և այս խնդիրը լուծեցին շատ արագ, հերթը ձերն է:
Մուտքային տվյալներ
Առաջին տողում տրված են
n-ը և k-ն: Երկրորդ տողում տրված են մարդկանց գիտելիքների աստիճանները (0 ≤ Ai < ):Ելքային տվյալներ
Բաժանման առավելագույն հզորությունը:
Սահմանափակումներ
- Թեստերի առաջին խմբի համար
1 ≤ k ≤ n ≤ 1000։
- Թեստերի երկրորդ խմբի համար
1 ≤ k ≤ n ≤ 500 000։
Օրինակներ
Մուտք. | Ելք. |
4 2
2 3 4 1 | 3 |
6 3
2 2 2 4 4 4 | 4 |
Աղբյուրը. Մարզային 2020
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB