1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <array>
#include <iostream>
#include <map>

#define ll int_fast64_t

struct posredni_wynik
{
	ll wspolczynniki_od;
	ll suma;
};

ll pierwsze_wzmocnienie(ll od, ll po, ll wzmocnienie)
{
	if (!(od<= po))
	{
		return -1;
	}
	ll bitow_w_od = __builtin_popcountll(od);
	if (bitow_w_od == wzmocnienie)
	{
		return od;
	}
	else if (bitow_w_od < wzmocnienie)
	{
		ll bit = 1;
		ll wynik = od;
		while (__builtin_popcountll(wynik) < wzmocnienie)
		{
			if (!(bit & wynik))
			{
				wynik += bit;
			}
			bit <<= 1;
		}
		if (wynik <= po)
		{
			return wynik;
		}
		return -1;
	}
	else
	{
		ll bit = 1;
		ll wynik = od;
		while (__builtin_popcountll(wynik) > wzmocnienie)
		{
			if (bit & wynik)
			{
				wynik -= bit;
			}
			bit <<= 1;
		}
		while (!(wynik & bit))
		{
			bit <<= 1;
		}
		wynik += bit;
		if (wynik <= po)
		{
			return wynik;
		}
		return -1;
	}
}

ll najmniejsze_wzmocnienie(ll od, ll po)
{
	if (od == 0)
	{
		return 0;
	}
	for (ll i = 1; i <= 61; ++i)
	{
		ll wynik = pierwsze_wzmocnienie(od, po, i);
		if (wynik != -1)
		{
			return i;
		}
	}
	return 0;
}

ll najwieksze_wzmocnienie(ll od, ll po)
{
	if (po == 0)
	{
		return 0;
	}
	for (ll i = 61; i > 0; --i)
	{
		ll wynik = pierwsze_wzmocnienie(od, po, i);
		if (wynik != -1)
		{
			return i;
		}
	}
	return 0;
}

int main()
{
	ll bitow;
	ll najw_wspolczynnik;
	std::map<ll, posredni_wynik> posrednie_wyniki;
	std::map<ll, posredni_wynik> nastepne_wyniki;
	std::array<ll, 205> bity;

	std::cin >> bitow >> najw_wspolczynnik;
// 	std::cerr << bitow << ' ' << najw_wspolczynnik << ' ' << std::endl;
	
	for (int i = 0; i < bitow; ++i)
	{
		std::cin >> bity[i];
// 		std::cerr << bity[i] << std::endl;
	}
	
	posrednie_wyniki[0] = {0, 0};
	
	for (int bit = 0; bit < bitow; ++bit) 
	{
// 		std::cerr << 'a' << std::endl;
		nastepne_wyniki.clear();
		for (auto it = posrednie_wyniki.begin(); it != posrednie_wyniki.end(); ++it)
		{
			ll wz_od = najmniejsze_wzmocnienie(it->second.wspolczynniki_od, najw_wspolczynnik);
			
			ll wz_do = najwieksze_wzmocnienie(it->second.wspolczynniki_od, najw_wspolczynnik);
// 			std::cerr <<  it->second.wspolczynniki_od << ',' << najw_wspolczynnik << '^' << wz_od << ' ' << wz_do <<  std::endl;
			for (ll wzmocnienie = wz_od; wzmocnienie <= wz_do; ++wzmocnienie)
			{
				ll wspolczynnik = pierwsze_wzmocnienie(it->second.wspolczynniki_od, najw_wspolczynnik, wzmocnienie);
// 			std::cerr <<  it->second.wspolczynniki_od << ',' << najw_wspolczynnik << '^' << wzmocnienie << ' ' << wspolczynnik <<  std::endl;
				if (wspolczynnik == -1)
				{
					continue;
				}
				ll suma = it->second.suma + wzmocnienie * bity[bit];
				auto istniejacy_wynik = nastepne_wyniki.find(wspolczynnik);
				if (istniejacy_wynik == nastepne_wyniki.end() || istniejacy_wynik->second.suma < suma)
				{
					nastepne_wyniki[wspolczynnik] = {wspolczynnik + 1, suma};
				}
			}
		}
// 		std::cerr << 'd' << std::endl;
		posrednie_wyniki.clear();
		ll najwieksza_suma = 0;
		for (auto it = nastepne_wyniki.begin(); it != nastepne_wyniki.end(); ++it)
		{
			if (it == nastepne_wyniki.begin() || it->second.suma > najwieksza_suma)
			{
				posrednie_wyniki[it->first] = it->second;
				najwieksza_suma = it->second.suma;
			}
		}
	}
	
	std::cout << posrednie_wyniki.rbegin()->second.suma << std::endl;
}