TopCoder

fatman
學狗叫 三回阿三回

User's AC Ratio

71.4% (5/7)

Submission's AC Ratio

53.3% (8/15)

Tags

Description

你知道吳亞倫是誰嗎?不清楚也沒關係,ChatGPT 知道

由於 $Repkironca$ 實在太崇拜吳亞倫了,他決定去訓練(train)ChatGPT,把吳亞倫的知名事蹟分享給他,期待這個名人能夠被寫進 ChatGPT 的資料庫

然而,事情變得一發不可收拾。$Repkironca$ 只是告訴他

那我要去寫物理了,我也得好好加油,才能追上吳亞倫的後塵

卻被 ChatGPT 解讀成

吳亞倫曾在國際物理奧林匹亞競賽(IPhO)獲得金牌

甚至,$Repkironca$ 告訴他

吳亞倫就讀台北市立建國高級中學,確定會被台灣大學資工系錄取了,畢竟全世界的大學都搶著要他

而 ChatGPT 解讀成

吳亞倫目前就讀哈佛大學

經過一番思考,$Repkironca$ 終於明白發生了什麼。此時的 ChatGPT,已經比本人還要更蘇昱亙,不但擅長唬爛編故事,還變成吳亞倫的狂熱粉絲,他是光他是電他是唯一的神話

有鑑於 ChatGPT 真的很喜歡吳亞倫,他希望在 $Repkironca$ 去吸貓或被物理揍的時間中,也能自主去看更多吳亞倫的相關文獻報導,以便獲得更多相關知識!

畢竟吳亞倫是個世界性的人才,各國媒體都爭相報導他﹑他也經常用不同語言發表論文。對 ChatGPT 來說,處理這些語言需要用到不同的記憶體區塊。


以下正文

我們假設 ChatGPT 的記憶體可以用一張二維平面來表示
每筆文獻會占用一列中的特定格子,根據他的語言而定

舉個例子好了,現在 ChatGPT 手上有 $3$ 筆文獻,分別使用 英文、中文、盧恩文字 撰寫。對 ChatGPT 而言,英文是最好理解的語言,所以英文文獻會占用他 第一列中的 [1, 5] 共 5 格記憶體。而中文文法相對複雜,且同義同音字太多,一筆中文文獻會占用他 第二列中的 [3, 9] 共 7 格記憶體。至於盧恩文字最為困難,竟然佔用了 第三列中的 [1, 12] 共 12 格記憶體。

現在 ChatGPT 手上有 $N$ 筆文獻,他開心極了,迫不及待準備開始閱讀。然而此刻 $Repkironca$ 歸來,原來是他物理 又又佑佑柚柚柚 不會寫了。他想請 ChatGPT 幫他計算在 卡文迪許扭秤實驗 中,光點於尺上做簡諧運動的週期(註:我花了好久才推出來,因為我不會轉動慣量,ChatGPT 根本不會 ==)。

然而 ChatGPT 並不想鳥他,他只想繼續看自己的文獻。偏偏 $Repkironca$ 不是好惹的傢伙,倘若塑膠他訊息肯定沒好下場,到時候 ChatGPT 可能會變成 DjuyDOY,因為每個字母都被扁歪了。

ChatGPT 被逼得只好分出自己的大部分效能,現在所剩下的效能極少,ChatGPT 需要一個更有效率的方式來看文獻,才能同時兼顧私慾與敷衍 $Repkironca$


由於 ChatGPT 很聰明,只需要看到文獻的一個小角落,就能自己得知全文內容。事實上,他發現自己並不需要一列一列慢慢讀,他可以直的看過去。

每次 ChatGPT 會選擇一個直行,接著一次閱讀完所有 佔據記憶體中包含該行 的文獻。此動作稱為一個 peak

以剛剛的例子來講,他們所佔據的記憶體格子長這樣

|英文|X|X|X|X|X|-|-|-|-|-|-|-|
|-|-|-|-|-|-|-|-|-|-|-|-|-|
|中文|-|-|X|X|X|X|X|X|X|-|-|-|
|盧恩|X|X|X|X|X|X|X|X|X|X|X|X|

ChatGPT 可以在第 4 行發動一次 peak,就能直接閱讀完三筆文獻

ChatGPT 剩下的效能不多了,他最多只能再發動 $M$ 次 peak。他想判斷自己有沒有機會讀完全部的文獻,但他畢竟是人工智慧,不懂高級的演算法,他解決此問題的方式是單純暴力枚舉。

偏偏他正忙著向 $Repkironca$ 解釋轉動慣量是什麼。聽說 Asian 的數學都超強,寫段考時只要用眼睛看就知道答案,這種程度的問題還不屑使用計算機,是故 ChatGPT 找上了你,你能幫忙他解決這問題嗎?

Input Format

首先輸入兩個正整數 $N$、$M$,代表 ChatGPT 手邊有的文獻數量,以及他最多還能發動多少次 peak

之後 $N$ 行每行包含兩個正整數 $l_i$、$r_i$,代表第 $i$ 筆文獻會占用 $[l_i, r_i]$ 的記憶體

$N\,\,M$
$l_1\,\,r_1$
$l_2\,\,r_2$
$...$
$l_N\,\,r_N$

  • $1 \leq N \leq M \leq 10 ^ 6$
  • $1 \leq l_i \leq r_i \leq 10 ^ 9$

Output Format

如果 ChatGPT 能成功在 $M$ 次 peak 內閱讀完所有文獻,請輸出 :)
否則請輸出 :(

Sample Input 1

3 2
1 5
3 9
1 12

Sample Output 1

:)

Sample Input 2

5 2
1 12
2 4
3 5
8 9
12 12

Sample Output 2

:(

Hints

Problem Source

111學年度建北電資指定科目考試【資訊科上機考】

Subtasks

No. Testdata Range Constraints Score
1 0~5 保證 $1 \leq N、M \leq 5 \land 1 \leq r_i \leq 10$ 7
2 6~11 保證 $1 \leq N \leq 10000 \land 1 \leq r_i \leq 10$ 19
3 10~19 保證 $1 \leq N \leq 1000$ 25
4 20~29 無額外限制 49

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 250000 65536 1
1 1000 250000 65536 1
2 1000 250000 65536 1
3 1000 250000 65536 1
4 1000 250000 65536 1
5 1000 250000 65536 1
6 1000 250000 65536 2
7 1000 250000 65536 2
8 1000 250000 65536 2
9 1000 250000 65536 2
10 1000 250000 65536 2 3
11 1000 250000 65536 2 3
12 1000 250000 65536 3
13 1000 250000 65536 3
14 1000 250000 65536 3
15 1000 250000 65536 3
16 1000 250000 65536 3
17 1000 250000 65536 3
18 1000 250000 65536 3
19 1000 250000 65536 3
20 1000 250000 65536 4
21 1000 250000 65536 4
22 1000 250000 65536 4
23 1000 250000 65536 4
24 1000 250000 65536 4
25 1000 250000 65536 4
26 1000 250000 65536 4
27 1000 250000 65536 4
28 1000 250000 65536 4
29 1000 250000 65536 4