#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maksimalna(int max){
    int max1 = -1000;
    if(max>max1){
        max1=max;
    }
    return max1;
}

int racunanje(vector <int> potrebni, string str2){
    //int maksimalna_vrednost;
    vector <int> maxvrednosti;
    int duzina = potrebni.size() - 1;
    for(int g = 0; g<duzina; g++){
        for(int q =0; q<potrebni.size(); q++){
        //if(q<q+1]){
            //break;
        //}
    }
        if(potrebni[0] - (potrebni[potrebni.size()-1]) > (potrebni[potrebni.size()-1])-potrebni[0]){
            potrebni[0]-= (potrebni[potrebni.size()-1]);
            potrebni.pop_back();
        }else{
            potrebni[potrebni.size()-1] -= potrebni[0];
            potrebni.erase(potrebni.begin());
        }

        int maksimalna_vrednost = maksimalna(potrebni[0]);
        maxvrednosti.push_back(maksimalna_vrednost);
        //sort(maxvrednosti.begin(), maxvrednosti.end());
        return maxvrednosti[0];

    }  
    
}

int ispitivanje(string kombinacija, vector <int> moci, string slova2, vector <int> max){
    vector<int> potrebne_moci {};
    int maks;
    for(char r ='a'; r<='z'; r++){
        for(int t=0; t<moci.size(); t++){
            if(kombinacija[t]==r){
                //potrebne_moci.push_back(moci[t]);
                for(int h = 0; h<slova2.length(); h++){
                    if(kombinacija[t]==slova2[h]){
                        potrebne_moci.push_back(moci[h]);
                    }
                }
            }
        }
    }
    return racunanje(potrebne_moci, kombinacija);
    //cout<<maksimalna_vrednost;

}

int var1(string ulaz, int k,  vector <int> moci, string slova2, vector<int> max, string izlaz = "")
{
    vector <int> max58;
	if (k == 0) {
        
        int max4 = ispitivanje(izlaz, moci, slova2, max);
        max58.push_back(max4);
        sort(max58.rbegin(), max58.rend());
        //cout<<max58[0];
		return max58[0];
	}
	else {
		string pom;
		for (int i = 0; i < (int)ulaz.size(); i++) {
			pom = ulaz;
			pom.erase(pom.begin() + i);
			var1(pom, k - 1,  moci,slova2,max, izlaz + ulaz[i]);
		}
	}

}

int main(){

    int n, k, moc;
    cin>>n>>k;
    string slova;
    vector <int> moci;
    vector <int> max67;
    vector <int> max;
    char g = 'a';

    for(int w = 0; w<n; w++){
        cin>>moc;
        moci.push_back(moc);
        slova.push_back(g);
        g++;
    }

    string slova2 = slova;
    //cout<<slova<<endl;
    max67.push_back(var1(slova, k, moci, slova2, max));
    cout<<(max67[0]/2)/1000000;


    return 0;
}