<<來自新世界 - 對抗虛偽的神>>這部動畫是kerker這幾年來認為最最好看的一部!!在kerker心裡是神作等級的!!!!裡面描述了1000年後的人類世界…主角們住在神棲66町 , 這城鎮劃分為3000*3000個小方格以方便管理 , 左上角那一格是(1,1) , 右下角那格則是(3000,3000) .
城鎮外則住了許多怪異的生物 , 最主要的是化鼠這一個族群 , 化鼠族群日益壯大 , 就在今晚 , 他們打算攻進人類的城鎮裡!!!但是人類們可不是好惹的 , 在1000年後的世界 , 人類擁有"咒力"這一項超強的武器 , 當人類使用咒力時 , 可以把距離這位人類10步以內的化鼠全部消滅!!(他不會打到人類同伴的!!否則….請看動畫XD)假設人類所在的座標是(x,y) , 化鼠所在的座標是(a,b) , 則絕對值(x-a) + 絕對值(y-b)只要小於等於10就可以把那隻化鼠消滅!!
大戰才剛開始 , 化鼠軍隊挾著大量的優勢進攻 , 數以萬計的化鼠不斷奔來 , 反觀人類部落 , 有能力防守的卻只有不到1000人…能請你幫忙算算人類到底能消滅幾隻化鼠嗎??
請注意 : 此題的input非常的大 , 切勿使用cin做讀取. 建議寫之前一定要先估算複雜度.
有多組測資，每組測資第一行有兩個數字H和M , H代表有多少個人類能進行防禦 , M代表有多少隻化鼠在地圖上.(0<=H<1000 , 0<=M<=10^6)
接下來H行 , 每行為一個人類所在的座標x y (1<=x,y<=3000) , 接下來M行每行代表一隻化鼠的座標x y (1<=x,y<=3000) . 座標皆有可能重複!!(表示一個座標格內可以有多個人和多隻化鼠)
每組測資輸出人類能殺死幾隻化鼠 , 一組測資輸出一行.