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

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

你和對手各有 $N$ 匹馬，要進行 $N$ 場比賽。一匹馬只限出場一次，同場比賽中速度較快的馬獲勝。若兩匹馬速度一樣，則算平手。你可以決定你的馬匹的出場順序；而你的對手，就如同齊王，會在第一場比賽出速度最快的馬，第二場出次快的馬，$\dots$，第 $N$ 場出速度最慢的馬。

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

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