题目描述
题目译自 PA 2019 Runda 1 Muzyka pop
给定 n 个整数 a1,a2,…,an 和一个整数 m。请找到 n 个非负整数 b1,b2,…,bn,满足 0≤b1<b2<…<bn≤m 并且 i=1∑npopcount(bi)⋅ai 的值最大,其中 popcount(x) 为 x 在二进制下的 1 的个数。
输入格式
第一行两个整数 n,m。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
输出一行一个整数,即 i=1∑npopcount(bi)⋅ai 的最大值。
样例 1
3 5
2 -1 3
9
可以取 b1=3,b2=4,b3=5,则答案为 2×2+(−1)×1+3×2=9。
3 2
1 1 -1
0
数据范围与提示
1≤n≤200,n−1≤m≤1018,1≤∣ai∣≤1014