g774: 校隊 (School Team)
Tags :
Accepted rate : 67人/79人 ( 85% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-12-02 12:49

Content

學校組織短跑接力賽校隊,需要從 $N + M$ 個班級裡面選出 $N$ 名男生和 $M$ 名女生。為了使每個班級都有參與感,每班都要派出一人參加,而且由於是校隊,派出的學生必須是該班級同性別中跑百米最快的人。小明身為體育組長,想要選出這 $N$ 男 $M$ 女 使得全隊跑百米的總時間越短越好,請幫助他計算出答案。
以下表為例,學校有四個班級,每班的男女生最佳成績如表所示。若需要從四個班級中選出二男二女,則最佳的選法為 1、3 班派女生,2、4 班派男生,時間總和為 1+2+2+4=9。


班級 男生最佳成績 女生最佳成績
  1           3                1

  2           2                1

  3           4                2

  4           4                4

Input

第一行有兩個正整數 $N$ 和 $M$ $(1 \leq N , M \leq 2 × 10^3)$,分別表示要選出 $N$ 名男生和 $M$ 名女生。接下來 $N + M$ 行每行都有兩個正整數 $B$ 和 $G$ $(1 \leq B, G \leq 10^4 )$,分別表示每一班級中男生和女生跑百米的最短時間。同一行的整數間均以空白間隔。

Output

請輸出一個正整數,表示選出 $N$ 名男生和 $M$ 名女生跑百米的最短總時間。

Sample Input #1
2 2
3 1
4 2
2 1
4 4
Sample Output #1
9
Sample Input #2
2 3
4 2
2 1
4 4
1 1
5 4
Sample Output #2
12
Sample Input #3
1 1
5 2
2 5
Sample Output #3
4
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (5%): 1.0s , <1K
不公開 測資點#1 (5%): 1.0s , <1K
不公開 測資點#2 (5%): 1.0s , <1K
不公開 測資點#3 (5%): 1.0s , <1K
不公開 測資點#4 (5%): 1.0s , <1K
不公開 測資點#5 (5%): 1.0s , <1K
不公開 測資點#6 (5%): 1.0s , <1K
不公開 測資點#7 (5%): 1.0s , <1M
不公開 測資點#8 (5%): 1.0s , <1M
不公開 測資點#9 (5%): 1.0s , <1K
不公開 測資點#10 (5%): 1.0s , <1K
不公開 測資點#11 (5%): 1.0s , <1M
不公開 測資點#12 (5%): 1.0s , <1M
不公開 測資點#13 (5%): 1.0s , <1M
不公開 測資點#14 (5%): 1.0s , <1M
不公開 測資點#15 (5%): 1.0s , <1M
不公開 測資點#16 (5%): 1.0s , <1M
不公開 測資點#17 (5%): 1.0s , <1M
不公開 測資點#18 (5%): 1.0s , <1M
不公開 測資點#19 (5%): 1.0s , <1M
Hint :

此題目測資分成三組,每組測資有多筆測試資料,需答對該組所有測試資料才能獲得該組分數,各組詳細限制如下。
第一組 (30分):$N, M \leq 10$。
第二組 (25分):$N, M \leq 10^2$。
第三組 (45分):沒有特別限制 。

Tags:
出處:
TOI練習賽202111潛力組 [管理者: fire5386(Penguin07) ]


ID User Problem Subject Hit Post Date
31522 wubaie(小億) g774
13 2022-08-05 22:05
28384 yes51851823@...(wseds) g774
389 2021-12-06 19:12
28365 r1cky(tour1st) g774
Java 解題心得
384 2021-12-05 12:34