The contest is ended. New submissions will be treated as correction submissions and will not be counted in the contest.

题目描述

史蒂夫回到了自己的村庄。

现在村庄有 $n$ 个防御点坐标 $(x_i,y_i)$，每个防御点需要至少 $k_i$ 个铁傀儡才能形成有效保护。制造一个铁傀儡需要 $4$ 个铁块和 $1$ 个雕刻南瓜，史蒂夫有 $I$ 个铁块，$P$ 个雕刻南瓜。但由于刻意的游戏设计，铁傀儡只能在 $(0,0)$ 制造，且制造耗时等于制造点到防御点的曼哈顿距离的平方。

铁傀儡的移动速度为 $1$ 格 $/$ 单位时间，而且只有所有可以制造的铁傀儡制造完成后，所有铁傀儡才能开始移动。

现在需要求出铁傀儡最多能有效保护的防御点数量和这些防御点达成有效保护的最短时间。

输入格式

第一行三个整数 $I,P,n$。

接下来 $n$ 行每行三个整数 $x_i,y_i,k_i$。

输出格式

两个整数，分别是最多能有效保护保护的防御点数量和这些防御点达成有效保护的最短时间。

输入输出样例

20 5 3
1 2 2
3 1 1
-2 -2 3

2 29

说明 / 提示

【样例解释】

$20\div4=5$，最多只能制造 $5$ 个铁傀儡，为了减少保护时间，选择与 $(0,0)$ 曼哈顿距离较近的 $(1,2)$ 和 $(3,1)$，制造需要 $(1+2)^2+(3+1)^2=25$ 单位时间，移动需要 $\max((1+2),(3+1))=4$ 单位时间，共 $29$ 单位时间。

【数据范围与约定】

对于 $100\%$ 的数据，$1 \le I,P \le 1000,1 \le n \le 20,1 \le |x|,|y| \le 1000,1 \le k \le 10$。