3291 - Alice与能源计划

在梦境中，Alice来到了火星。不知为何，转眼间Alice被任命为火星能源部长，并立刻面临着一个严峻的考验。为 了方便，我们可以将火星抽象成平面，并建立平面直角坐标系。火星上一共有N个居民点。每个居民点认为是平面 上的一个点。第i个居民点的坐标为(Xi,Yi），对能源的需求量为Poweri。每个居民点消耗的能源由它附近的发电 站提供。由于技术原因，一个居民点消耗的所有能源必须来自同一座发电站。自人类移民火星之初，政府就有一个 规模宏大的发电站建设计划。按照这个计划，政府将在火星上建立M座发电站，这M座发电站将是火星居民的全部能 量来源。其中，第i座发电站的坐标为(xi,yi)，产生能量的上限值为Limiti，建设费用为Pricei。同样由于技术原 因，第i座发电站只能为与它的距离不超过Ri的居民点提供能源。然而，由于政府的财政状况一直十分紧张，截至 目前，这M座发电站中只有少量建成并投入使用，多数的发电站尚未开始建设。Alice的任务是修改这个计划，使得 它更符合实际情况。根据新的规定，一座发电站产生的所有能源必须提供给同一个居民点。Alice知道这个规定意 味着N个居民点消耗的能源将分别由N座不同的发电站提供，而且为第i个居民点提供能源的那座发电站的Limit值一 定不小于Poweri。Alice需要在原计划的M座发电站中选择恰好N座发电站，并完全放弃剩余的M-N座发电站，使得这 N座发电站能够满足N个居民点的需要。对于一个可行的方案，设方案中选择的N座发电站构成集合S，而已经建成的 发电站构成集合T，那么定义这个方案的代价为即，一个方案的代价等于被选择的且尚未建成的发电站的建设费用 之和加上没有被选择的且已经建成的发电站的建设费用之和。在所有可行方案中，你必须帮助Alice找到代价最小 的方案，并将选择的N座发电站按编号从小到大的顺序输出。如果代价最小的方案不唯一，则输出其中字典序最小 的方案。 注意，输入文件包含多组测试数据。

第一行包含一个正整数T，表示有T组测试数据。接下来依次是T组测试数据。 每组测试数据的第一行包含两个整数N、M。 接下来N行，每行3个整数：Xi、Yi、Poweri。 再接下来M行，每行6个整数：xi、yi、Limiti、Pricei、Ri、Finishedi。 若Finishedi=1，表示第i座发电站已经建成；否则Finishedi=0，表示第i座发电站尚未开始建设。 1≤N≤400，1≤M≤500，1≤T≤10，0≤xi,yi,Xi,Yi,Pricei≤10000， 1≤Ri,Poweri,Limiti≤10000。不同的居民点或发电站的坐标有可能重合。 关于方案的字典序的大小关系的说明： 设方案A选择的N座发电站的编号从小到大依次为A1,A2,…,AN； 设方案B选择的N座发电站的编号从小到大依次为B1,B2,…,BN。 我们称方案A比方案B字典序更小，当且仅当存在正整数i，满足1≤i≤N， 使得对任意1≤k≤i-1有Ak=Bk，且Ai<Bi。

对于每组测试数据： 若存在可行方案则输出两行。第一行为一个整数，表示最小代价； 第二行是若干个递增的整数，表示字典序最小的最优方案选择的发电站的编号。 若不存在可行方案，则仅输出一行为一个整数-1。