某購(gòu)物城有m個(gè)商鋪，現(xiàn)決定舉辦一場(chǎng)活動(dòng)選出人氣最高店鋪?；顒?dòng)共有n位市民參與，每位市民只能投一票，但1號(hào)店鋪如果給該市民發(fā)放q元的購(gòu)物補(bǔ)貼，該市民會(huì)改為投1號(hào)店鋪。

請(qǐng)計(jì)算1號(hào)店鋪需要最少發(fā)放多少元購(gòu)物補(bǔ)貼才能成為人氣最高店鋪(即獲得的票數(shù)要大于其他店鋪)，如果1號(hào)店鋪本身就是票數(shù)最高店鋪，返回0。

輸入描述:

第一行為小寫(xiě)逗號(hào)分割的兩個(gè)整數(shù)n，m，其中第一個(gè)整數(shù)n表示參與的市民總數(shù)，第二個(gè)整數(shù)m代表店鋪總數(shù)，1<= n, m <= 3000.

第2到n+1行，每行為小寫(xiě)逗號(hào)分割的兩個(gè)整數(shù)p，q，表示市民的意向投票情況，其中每行的第一個(gè)整數(shù)p表示該市民意向投票給p號(hào)店鋪，第二個(gè)整數(shù)q表示其改投1號(hào)店鋪所需給予的q元購(gòu)物補(bǔ)貼，1 <= p <= m,1<= q <= 10^9.不考慮輸入的格式問(wèn)題

輸出描述

1號(hào)店鋪需要最少發(fā)放購(gòu)物補(bǔ)貼金額。

示例1

輸入:

5,5

2,10

3,20

4,30

5,40

5,90

輸出:

50

說(shuō)明:

有5個(gè)人參與，共5個(gè)店鋪。

如果選擇發(fā)放 10元+20元+30元=60元 的補(bǔ)貼來(lái)?yè)?.3.4號(hào)店鋪的票，總共發(fā)放了60元補(bǔ)貼

(5號(hào)店鋪有2票，1號(hào)店鋪要3票才能勝出)

如果選擇發(fā)放 10元+40元=50元 的補(bǔ)貼來(lái)?yè)?.5號(hào)店鋪的票，總共發(fā)放了50元補(bǔ)貼

(搶了5號(hào)店鋪的票后，現(xiàn)在1號(hào)店鋪只要2票就能勝出)

所以最少發(fā)放50元補(bǔ)貼

示例2

輸入:

5,5

2,10

3,20

4,30

5,80

5,90

輸出:

60

說(shuō)明:

有5個(gè)人參與，共5個(gè)店鋪.

如果選擇發(fā)放 10元+20元+30元=60元 的補(bǔ)貼來(lái)?yè)?.3.4號(hào)店鋪的票，總共發(fā)放了60元補(bǔ)貼(5號(hào)店鋪有2票，1號(hào)店鋪要3票才能勝出)

如果選擇發(fā)放 10元+80元=90元 的補(bǔ)貼來(lái)?yè)?,5號(hào)店鋪的票，總共發(fā)放了90元補(bǔ)貼(搶了5號(hào)店鋪的票后，現(xiàn)在1號(hào)店鋪只要2票就能勝出)所以最少發(fā)放60元補(bǔ)貼

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

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

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

JavaScript實(shí)現(xiàn)：https://blog.csdn.net/misayaaaaa/category_12199270.html

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