점수 인플레이션 더블릿

#include <stdio.h>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int arr[20000] = { 0 };
int dp[20000] = { 0 };
 
int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    getchar();
 
    //시간초과를 막기 위해 입력을 받을때마다 연산 진행
    for (int i = 1; i <= n; i++) {
        int time, score,idx=0,k;
        scanf("%d %d", &score, &time);
                
        //시간초과 막기 위해 딱 해당되는 부분만 수를 채운다
        k = 1;
        while (k * time <= m) {
            arr[k*time] = k*score;
            k++;
        }
        for (int j = 0; j <= m; j++) {
            int maxMoney = 0,k=1;
            //시간초과 막기 위해 딱 해당되는 부분만 비교해준다
            while (k*time <= j) {
                maxMoney = max(maxMoney, arr[k*time] + dp[j - k*time]);
                k++;
            }
            dp[j] = max(dp[j], maxMoney);
        }        
    }
    int numMax = 0;
    for (int j = 0; j <= m; j++) {
        numMax = max(numMax, dp[j]);
    }
    printf("%d", numMax);
}