小明每周上班都會(huì)拿到自己的工作清單，工作清單內(nèi)包含n項(xiàng)工作，每項(xiàng)工作都有對(duì)應(yīng)的耗時(shí)時(shí)間（單位h）和報(bào)酬,

工作的總報(bào)酬為所有已完成工作的報(bào)酬之和，那么請(qǐng)你幫小明安排一下工作，保證小明在指定的工作時(shí)間內(nèi)工作收入最大化。

輸入描述

輸入的第一行為兩個(gè)正整數(shù)T，n。

T代表工作時(shí)長(zhǎng)（單位h，0<T<1000000），n代表工作數(shù)量（1<n≤3000）。

接下來是n行，每行包含兩個(gè)整數(shù)t，w。

t代表該工作消耗的時(shí)長(zhǎng)（單位h，t>0）,w代表該項(xiàng)工作的報(bào)酬。

輸出描述

輸出小明制定工作時(shí)長(zhǎng)內(nèi)工作可獲得的最大報(bào)酬。

示例一

輸入

40 3

20 10

20 20

20 5

輸出

30

————————————————

版權(quán)聲明：本文為CSDN博主「MISAYAONE」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接及本聲明。

原文鏈接：https://renjie.blog.csdn.net/article/details/128331812

Java 實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/128331812

Python實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/128331796

C++ 實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/128331782

JavaScript實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/129027295

C實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/129250677