#include
<
iostream
>
using
namespace
std;
#define
N 100001
int
nk[
11
], dk[
11
], n, m, ans[N], num[N];
int
main(){
while
( scanf(
"
%d%d
"
,
&
m,
&
n )
!=
EOF ){
for
(
int
i
=
0
; i
<
n;
++
i ) scanf(
"
%d%d
"
, nk
+
i, dk
+
i );
for
(
int
i
=
0
; i
<=
m;
++
i ) ans[i]
=
0
; ans[
0
]
=
1
;
for
(
int
i
=
0
; i
<
n;
++
i ){
for
(
int
j
=
0
; j
<=
m;
++
j ) num[j]
=
0
;
for
(
int
j
=
dk[i]; j
<=
m;
++
j )
if
(
!
ans[j]
&&
ans[j
-
dk[i]]
&&
num[j
-
dk[i]]
<
nk[i] ){
num[j]
=
num[j
-
dk[i]]
+
1
;
ans[j]
=
1
; }
}
int
res
=
m;
while
( ans[res]
==
0
&&
res
>=
1
) res
--
;
printf(
"
%d\n
"
, res );
}
return
0
;
}
posted on 2009-07-19 13:44
Darren 阅读(520)
评论(1) 编辑 收藏 引用 所属分类:
动态规划