一個(gè)設(shè)備由N種類型元器件組成(每種類型元器件只需要一個(gè)，類型type編號(hào)從0~N-1),每個(gè)元器件均有可靠性屬性reliability，可靠性越高的器件其價(jià)格price越貴。而設(shè)備的可靠性由組成設(shè)備的所有器件中可靠性最低的器件決定。給定預(yù)算S，購買N種元器件(每種類型元器件都需要購買一個(gè))，在不超過預(yù)算的情況下，請(qǐng)給出能夠組成的設(shè)備的最大可靠性.

輸入描述

S N // S總的預(yù)算，N元器件的種類

total // 元器件的總數(shù)，每種型號(hào)的元器件可以有多種:

此后有total行具體器件的數(shù)據(jù)

type reliability price / type 整數(shù)類型，代表元器件的類型編號(hào)從0 ~ N-1; reliabily 整數(shù)類型，代表元器件的可靠性: price 整數(shù)類型，代表元器件的價(jià)格

輸出描述

符合預(yù)算的設(shè)備的最大可靠性，如果預(yù)算無法買產(chǎn)N種器件，則返回 -1

備注

0 <= S,price <= 10000000

0 <= N <= 100

0 <= type <= N-1

0 <= total <= 100000

0 < reliability <= 100000

示例1：

輸入

500 3

6

0 80 100

0 90 200

1 50 50

1 70 210

2 50 100

2 60 150

輸出

60

說明

預(yù)算500，設(shè)備需要3種元件組成，方案類型0的第一個(gè)(可靠性80),

類型1的第二個(gè)(可靠性70).

類型2的第二個(gè)(可靠性60).

可以使設(shè)備的可靠性最大 60

示例2：

輸入

100 1

1

0 90 200

輸出

-1

說明

組成設(shè)備需要1個(gè)元件，但是元件價(jià)格大于預(yù)算，因此無法組成設(shè)備，返回-1

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

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

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

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

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