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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,t[20],w[20],a[20],ans=1234567921234576792ll;
mt19937 rd((unsigned ll)new char);
inline bool cmp(int x,int y){return t[x]<t[y];}
inline bool cmp2(int x,int y){return t[x]>t[y];}
inline bool cmp3(int x,int y){return w[x]<w[y];}
inline bool cmp4(int x,int y){return w[x]>w[y];}
ll calc(){
ll s=0,k=0,mx=0;
for(int i=1;i<=n;++i){
if(s+w[a[i]]>m){k+=mx;s=w[a[i]];mx=t[a[i]];}
else{s+=w[a[i]];mx=max(mx,t[a[i]]);}
}
return k+mx;
}
int main(){
cin>>m>>n;
for(int i=1;i<=n;++i)cin>>t[i]>>w[i];
for(int i=1;i<=n;++i)a[i]=i;
sort(a+1,a+n+1,cmp);ans=min(ans,calc());
sort(a+1,a+n+1,cmp2);ans=min(ans,calc());
sort(a+1,a+n+1,cmp3);ans=min(ans,calc());
sort(a+1,a+n+1,cmp4);ans=min(ans,calc());
while(1.0*clock()/CLOCKS_PER_SEC<=0.985){ans=min(ans,calc());shuffle(a+1,a+n+1,rd);}
cout<<ans<<'\n';
return 0;
}
|
