Problem 732

Standing on the shoulders of trolls

$N$ trolls are in a hole that is $D_{N}$ cm deep. The $n$ -th troll is characterized by:

the distance from his feet to his shoulders in cm, $h_{n}$
the length of his arms in cm, $l_{n}$
his IQ (Irascibility Quotient), $q_{n}$ .

Trolls can pile up on top of each other, with each troll standing on the shoulders of the one below him. A troll can climb out of the hole and escape if his hands can reach to the surface. Once a troll escapes he cannot participate any further in the escaping effort.

The trolls execute an optimal strategy for maximizing the total IQ of the escaping trolls, defined as $Q (N)$ .

Let
$r_{n} = [(5^{n} mod (10^{9} + 7)) mod 101] + 50$
$h_{n} = r_{3 n}$
$l_{n} = r_{3 n + 1}$
$q_{n} = r_{3 n + 2}$
$D_{N} = \frac{1}{\sqrt{2}} \sum_{n = 0}^{N - 1} h_{n}$ .

For example, the first troll ( $n = 0$ ) is $51$ cm tall to his shoulders, has $55$ cm long arms, and has an IQ of $75$ .

You are given that $Q (5) = 401$ and $Q (15) = 941$ .

Find $Q (1000)$ .

站在巨魔的肩膀上

$N$ 只巨魔（编号为 $0$ 至 $N - 1$ ）掉进了深度为 $D_{N}$ 厘米的洞中，其中编号为 $n$ 的巨魔有三项特征：

他的肩高为 $h_{n}$ 厘米；
他的臂长为 $l_{n}$ 厘米；
他的怒商（怒气商数，简称IQ）为 $q_{n}$ 。

巨魔们可以通过站在别的巨魔的肩膀上来搭起人梯，只要人梯最上方的巨魔的手臂能够够到地表，这只巨魔就能逃生。已经逃生的巨魔不能回洞中继续帮助其他巨魔逃生。

假设巨魔采用了能够使得所有逃出巨魔的IQ之和最高的策略，并记该策略下IQ之和为 $Q (N)$ 。

记
$r_{n} = [(5^{n} mod (10^{9} + 7)) mod 101] + 50$
$h_{n} = r_{3 n}$
$l_{n} = r_{3 n + 1}$
$q_{n} = r_{3 n + 2}$
$D_{N} = \frac{1}{\sqrt{2}} \sum_{n = 0}^{N - 1} h_{n}$ .

例如，第一只（编号为 $n = 0$ ）巨魔的肩高为 $51$ 厘米，臂长为 $55$ 厘米，IQ为 $75$ 。

已知 $Q (5) = 401$ ， $Q (15) = 941$ 。

求 $Q (1000)$ 。