洋菓子専門店ストレイキャッツではたくさんの猫が飼われている。猫の数があまりにも多いため、この店のスタッフである希は餌やりに困っていた。 いくつかの場所に餌を置いても、猫は貪欲なので最も近い餌に向かってしまい、一つの餌入れにたくさんの猫が集中してしまう。 あなたは希のために、できるだけ猫が集中しない餌の配置を求める問題を解くことにした。
問題を簡単にするため、猫は平面上の y>0 の部分にいて餌を置くまで動かないとする。 猫は N 個の集団に分かれていて、一箇所に何匹もいるかもしれない。 餌入れは y=0 上の M 点に固定してあり、この中からいくつか選んで餌を入れることになる。 餌を入れると、猫は(ユークリッド距離で)一番近い餌の入った餌入れに向かうが、同じ距離に二つあるときはx座標が小さいほうに向かうものとする。
この条件の下で、最も猫が集まっている餌入れの猫の数を最小化しなさい。
N M x1 y1 C1 ... xN yN CN x1 ... xM
入力の1行目には、2つの整数 N, M がスペース文字で区切られて与えられる。これらは、問題文で指定したとおりである。0 ≤ N ≤ 1000 および 1 ≤ M ≤ 1000 を満たす。
続く N 行には、それぞれの猫の集団について1行に1つずつ、集団の位置の x, y 座標を表す整数の組 (-10000 ≤ x ≤ 10000, 0 < y ≤ 10000)と何匹集まっているかを表す整数C(1 ≤ C ≤ 100000)が与えられる。
その後のM行には、それぞれの餌入れについて1行に1つずつ、餌入れの位置のx座標を表す整数(-10000 ≤ x ≤ 10000)が与えられる。 同じ点に、二つ以上の餌入れが存在することはない。
最も猫が集まっている餌入れの猫の数の最小値を出力せよ。
上記入力形式で複数のデータセットが与えられます。各データセットに対して上記出力形式で出力を行うプログラムを作成して下さい。
N, M がともに 0 のとき入力の終わりを示します。
3 3 -1 1 1 0 1 1 1 1 1 -3 0 3 5 5 7 3 5 -9 2 7 4 9 6 10 5 9 -9 7 9 0 -1 -2 -9 -8 0 0
2 20