回分類題庫
h098: F.田忌賽馬
關鍵字: NPSC 2011 高中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 89 Times / 71 Users | Submit : 456 Times / 87 Users | Accepted rate : 82%
題目加入時間 : 2012-11-04 02:31

Content: 简体中文

齊使者如梁,孫臏以刑徒陰見,說齊使。齊使以為奇,竊載與之齊。齊將田忌善而客待之。忌數與齊諸公子馳逐重射。孫子見其馬足不甚相遠,馬有上、中、下輩。於是孫子謂田忌曰:「君第重射,臣能令君勝。」田忌信然之,與王及諸公子逐射千金。及臨質,臏曰:「今以君之下駟與彼上駟,取君上駟與彼中駟,取君中駟與彼下駟。」既馳三輩畢,而田忌一不勝而再勝,卒得王千金。於是忌進孫子於威王。威王問兵法,遂以為師。

—『史記。孫子吳起列傳第五』

千年以前,孫臏靠著過人的智謀,巧妙地調整比賽順序,讓三戰皆墨的田忌翻身成兩勝一敗的贏家,也為自己贏得尊敬和重用。千年以後的今日,賽馬依然是熱門的活動,不過今天你要面對的是更困難的問題。

你和對手各有 N 匹馬,要進行 N 場比賽。一匹馬只限出場一次,同場比賽中速度較快的馬獲勝。若兩匹馬速度一樣,則算平手。

你可以決定你的馬匹的出場順序;而你的對手,就如同齊王,會在第一場比賽出速度最快的馬,第二場出次快的馬,· · ·,第 N 場出速度最慢的馬。

除此之外,你還可以決定比賽的時間,全部 N 場比賽都會在你選的這一天進行。在比賽之前,勤勞的你每天都會訓練你的每一匹馬;而你的對手自我感覺非常良好,因此不會訓練他的馬。每一匹馬的素質不同,我們用 ai 來表示第 i 匹馬的速度,用 bi 來表示第 i 匹馬的成長率。經過 m 天的訓練,你的第 i 匹馬在第 m+1 天的速度就會是ai +m×bi。對手的第 j 匹馬在每一天的速度都是cj。

現在你有你和對手共 2N 匹馬的資料,請決定訓練的天數 M,使得在第 M+1 天比賽的時候,你有一個出場順序可以贏得 N 場比賽中的至少 K 場(不包含平手)。

Input:

第一行有一個整數 T (T ≤ 100),代表接下來有幾組測試資料。

每一組測試資料的第一行有兩個數字,N 和 K。

接下來 N 行是你的馬匹的資料,每一行有兩個整數,ai 和 bi,代表馬匹的速度和成長率。

再下來 N 行是對手的馬匹的資料,每一行有一個整數 cj,代表馬匹的速度。( 1 ≤ K ≤ N ≤ 10000, 0 ≤ ai, cj ≤ 100000000, 0 ≤ bi ≤ 100 )

Output:

對每筆測試資料輸出一個非負整數 M,代表訓練 M 天後在第 M + 1 天舉行賽馬你可以贏得至少 K 場。

如果有不只一個 M 滿足條件,請輸出最小的 M。如果沒有任何 M 滿足條件,請輸出 -1。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
3 2
1 2
2 1
3 2
0
3
4
1 1
1 0
2

Sample Output :

1
-1

Hint :

long long int

Author :

NPSC 2011 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum