记录编号	23565	评测结果	AAAAAAAAAAA
题目名称	[POI 1998] 最轻的语言	最终得分	100
用户昵称	Pom	是否通过	通过
代码语言	C++	运行时间	0.262 s
提交时间	2011-03-15 15:27:14	内存使用	76.55 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

const int oo=1000000000;

struct node
{
	int size,C;
	node *c[2],*f;
	inline void update()
	{
		size=1;
		if (c[0]) size+=c[0]->size;
		if (c[1]) size+=c[1]->size;
	}
};

struct Splay
{
	node P[4000000],*root;
	int ps;
	Splay()
	{
		ps=1;
		root=P;
		P->size=2;
		P->C=-oo;
		P->c[1]=P+1;
		P[1].size=1;
		P[1].C=oo;
		P[1].f=P;
	}
	inline int size()
	{
		return root->size-2;
	}
	inline void rotate(node *p,int d)
	{
		p->f->c[!d]=p->c[d];
		if (p->c[d]) p->c[d]->f=p->f;
		p->c[d]=p->f;
		if (p->f->f)
		{
			if (p->f==p->f->f->c[d]) p->f->f->c[d]=p;
			else p->f->f->c[!d]=p;
		}
		p->f=p->f->f;
		p->c[d]->f=p;
		p->c[d]->update();
		p->update();
	}
	void splay(node *p,node *goal)
	{
		while (p->f!=goal)
		{
			node *y=p->f;
			if (y->f==goal)
			{
				if (y->c[0]==p) rotate(p,1);
				else rotate(p,0);
				break;
			}
			if (p==y->c[0])
			{
				if (y==y->f->c[0])
				{
					rotate(y,1);
					rotate(p,1);
				}
				else
				{
					rotate(p,1);
					rotate(p,0);
				}
				continue;
			}
			if (y==y->f->c[1])
			{
				rotate(y,0);
				rotate(p,0);
			}
			else
			{
				rotate(p,0);
				rotate(p,1);
			}
		}
		if (!goal) root=p;
	}
	node* fin(node *p,int key,int now)
	{
		if (!p->c[0] && now+1==key) return p;
		if (p->c[0])
			if (p->c[0]->size+now+1==key) return p;
		if (!p->c[0]) return fin(p->c[1],key,now+1);
		if (p->c[0]->size+1+now<key) return fin(p->c[1],key,now+p->c[0]->size+1);
		else return fin(p->c[0],key,now);
	}
	node* find(int key)
	{
		return fin(root,key+1,0);
	}
	node* ins(node* &p,int key,node* from)
	{
		if (!p)
		{
			++ps;
			p=P+ps;
			p->C=key;
			p->size=1;
			p->f=from;
			return p;
		}
		if (p->C<key) return ins(p->c[1],key,p);
		return ins(p->c[0],key,p);
	}
	void insert(int key)
	{
		splay(ins(root,key,NULL),NULL);
	}
	void del(int l,int r)
	{
		splay(find(l-1),NULL);
		splay(find(r+1),root);
		root->c[1]->c[0]=NULL;
		root->c[1]->update();
		root->update();
	}
}T;

int tmp,re,w[27],n,k,i,j,ans=oo,now=0;
bool flag=true;

int main()
{
	freopen("naj.in","r",stdin);
	freopen("naj.out","w",stdout);
	scanf("%d%d",&n,&k);
	for (i=1;i<=k;i++)
		scanf("%d",&w[i]);
	for (i=1;i<=k;i++)
	{
		T.insert(w[i]);
		now+=w[i];
	}
	if (n==k) ans=now;
	for (;;)
	{
		int t1=0,t2=0,tt;
		tmp=T.find(1)->C;
		now-=tmp;
		T.del(1,1);
		for (i=1;i<=k;i++)
		{
			T.insert(w[i]+tmp);
			now+=w[i]+tmp;
		}
		if (T.size()>n) 
		{
			for (i=n+1;i<=T.size();i++)
				now-=T.find(i)->C;
			T.del(n+1,T.size()); 
		}
		if (now<ans && T.size()==n) ans=now;
		else
			if (T.size()<n) ans=oo;
			else break;
	}
	printf("%d\n",ans);
	return 0;
}