#P18305. Just Mining

Just Mining

Just Mining

矮人在深矿的底层发现了一些新的金矿床。把矿井底层看成平面,矿床的位置由点的多重集 P={p1,…,pM}P=\{p_1,\ldots,p_M\} 给出,第 ii 个矿床的预估价值是 viv_i。不同矿床可能具有相同坐标,但它们仍然是可以分别选择的不同矿床。

过度开采某些区域可能导致矿井不稳定甚至坍塌。矿工、地质学家和工程师共同找出了这些危险区域,它们由圆的多重集 C={c1,…,cN}C=\{c_1,\ldots,c_N\} 描述。第 ii 个圆有容量 fif_i,表示该圆所围成的闭圆盘内,包括圆周上的矿床,最多可以开采 fif_i 个。

请选出一部分矿床,使它们的价值总和最大,并且不超过任何一个圆的容量。形式化地,令 PiP_i 为位于第 ii 个闭圆盘中的矿床多重集,所选矿床集合 A⊆PA\subseteq P 必须满足

∣A∩Pi∣≤fi(1≤i≤N).|A\cap P_i|\le f_i\qquad(1\le i\le N).

保证所有圆可以划分成两个互不相交的族 C1,C2C_1,C_2,且每个族都满足层叠性质:同一族中,任意两个圆所围成的区域要么彼此分离,要么一个严格包含另一个;同一族中任意两个圆的圆周没有公共点。因此,同一族中不会出现相交、相切或重合的圆周。这里的“圆周没有公共点”不排除圆盘的严格包含。

这个划分并没有在输入中给出。圆的输入是多重集,允许出现相同的圆,只要仍然满足能分成上述两个族的保证。

输入格式

第一行包含两个整数 N,MN,M,分别表示圆和矿床的数量。

接下来 NN 行,每行包含四个整数 xi,yi,ri,fix_i,y_i,r_i,f_i,分别表示第 ii 个圆的圆心坐标、半径和容量。

接下来 MM 行,每行包含三个整数 xi,yi,vix_i,y_i,v_i,分别表示第 ii 个矿床的坐标和价值。不同矿床的坐标可以相同。

输入仅有一组数据。

输出格式

输出三行。

第一行输出所选矿床的最大可能价值总和。

第二行输出一个达到该最大价值的方案所选矿床数。

第三行输出这个方案中所有矿床的编号。矿床按照输入顺序从 11 开始编号。可以以任意顺序输出,每个编号最多出现一次。

如果存在多种最优方案,输出任意一种即可。

数据范围

  • 1≤N,M≤3001\le N,M\le300;
  • 所有坐标满足 −109≤xi,yi≤109-10^9\le x_i,y_i\le10^9;
  • 1≤ri,vi≤1091\le r_i,v_i\le10^9;
  • 1≤fi≤3001\le f_i\le300。

保证所有圆可以划分为两个满足上述条件的族。

样例 1

5 5
3 5 2 2
4 10 4 2
5 10 2 3
5 5 5 2
14 4 2 3
6 11 3
3 8 5
4 6 20
9 5 4
14 5 1
28
4
1 3 4 5

样例 2

3 2
4 7 2 2
4 8 1 1
8 7 1 1
4 7 5
4 8 4
5
1
1