Luogu - p1616 crazy herb picking

Background

The title is to commemorate LiYuxiang born .

Title Description

LiYuxiang He is a gifted child , His dream is to become the greatest doctor in the world . So , He wants to learn from the most prestigious doctor in the neighborhood . In order to judge his qualifications , Gave him a problem . The doctor took him to a cave full of herbs and said ：“ children , There are some different kinds of herbs in this cave , It takes some time to pick each , Each has its own value . I'll give you a period of time , In the meantime , You can pick some herbs . If you are a smart kid , You should be able to maximize the total value of the herbs you pick .”

If you are LiYuxiang, Can you finish the task ？

The difference between this question and picking herbs ：

1. Every herb can be picked without limit .

2. The variety of medicine is dazzling , It's a long time to collect medicine ！ Master, thank you for waiting ！

Input format

The first line of input has two integers , Each represents the total time that can be used to collect medicine  t And the number of herbs in the cave m.

The first  2 To the first (m+1)  That's ok , Two integers per line , The first (i+1)  The whole number of lines ai​,bi​  They represent the second day of picking  ii  The time to plant the herb and the value of the herb .

Output format

Output one line , This line contains only one integer , Within a specified time , The maximum total value of herbs available .

I/o sample

Input #1

70 3
71 100
69 1
1 2

Output #1

140

explain / Tips

Data scale and agreement

• about 30%  The data of , Guarantee m≤10^3 .
• about 100%  The data of , Guarantee 1≤m≤10^4,1≤t≤10^7, And 1≤m×t≤10^7,1≤ai​,bi​≤10^4.

Answer key ：

It's a complete knapsack problem , The only one ( This is not a dash , It's two ones ) The point to note is that the data range will become long long, Or it will explode 90. Have to say ,lg The previous data really H2O

Program ：

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[10010],b[10010],dp[10000010];
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	    cin>>a[i]>>b[i];
	for(int i=1;i<=n;i++)
	    for(int j=a[i];j<=m;j++)
	        dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
	cout<<dp[m];
	return 0;
}