Maximizing Spaceship Damage Through Chain Reaction

In this problem, you are given an initial platform at point \((0,0)\) equipped with several \(\alpha\) launchers. You may activate exactly \(k\) of the available \(\alpha\) launchers (from a total of \(m\) launchers) in some order. Each \(\alpha\) launcher on the initial platform fires a single energy beam upward (i.e. in the northeast direction at \(45^\circ\)) with an energy value equal to its given value. The beam travels along the ray

$$(x,y)=(0,0)+t(1,1), \quad t\ge0.$$

The map contains \(n\) floating platforms. Each floating platform is a point \((x,y)\) and carries either an \(\alpha\) launcher or a \(\beta\) launcher. Their behavior is defined as follows:

• For an \(\alpha\) launcher: if it is installed on the upper part of the platform, when activated it fires a beam in the northeast direction (i.e. along \((1,1)\)) with energy value \(\alpha_i\); if installed on the lower part, it fires in the southeast direction (i.e. along \((1,-1)\)) with energy \(\alpha_i\).
• For a \(\beta\) launcher: regardless of its position, when activated it fires two beams simultaneously—one in the northeast direction and one in the southeast direction, each with energy \(\beta_i\).

A beam travels in a straight line and stops when it meets an object (either a platform or the enemy spaceship). When a beam hits a floating platform:

• If the platform has not been activated before (i.e. it has not provided its energy via a beam before), it becomes activated. The beam is absorbed by the platform and then (immediately) the launcher on that platform fires its beam(s) with energy equal to current beam energy + platform energy. That is, if a beam with energy \(E\) activates a platform with energy \(v\), the new beam(s) will have energy \(E+v\). Each platform activates at most once; subsequent beams hitting an activated platform are absorbed without effect.
• If the beam would hit the enemy spaceship, it stops and the spaceship takes damage equal to the beam’s current energy. (Note that a beam’s energy is the sum of the energies along its activation path.)

The enemy spaceship is represented by a vertical line segment located at \(x=wx\) with endpoints \((wx,sy)\) and \((wx,ty)\). When a beam from point \((s_x,s_y)\) traveling in direction \(d\) (either northeast or southeast) reaches \(x=wx\), its \(y\)-coordinate is computed by:

• If the beam is in the northeast direction: \(y = s_y + (wx - s_x)\).
• If the beam is in the southeast direction: \(y = s_y - (wx - s_x)\).

The beam hits the spaceship if and only if the computed \(y\)-coordinate is between \(sy\) and \(ty\) (inclusive). Additionally, note that if a beam encounters a platform along its travel path, it stops at the first encountered platform even if the platform has already been activated.

The twist: When firing the initial \(\alpha\) launchers from the initial platform, note that all these launchers fire from \((0,0)\) in the northeast direction. Consequently, if there is a floating platform on the line \(y=x\) (with \(0 < x < wx\)) that has not yet been activated, every beam from \((0,0)\) will first hit that platform. In this case, only the first fired launcher (the one you choose to fire first) will trigger a chain reaction, while subsequent beams will be absorbed by the already activated platform without generating extra beams.

Your task is to choose the order in which to fire exactly \(k\) of the \(\alpha\) launchers from the initial platform (given \(m\) available launchers, you may select any \(k\) and decide their firing order) so that the total damage inflicted on the enemy spaceship is maximized. It turns out that the optimal strategy is as follows:

1. If there exists a floating platform on the ray \(y=x\) (with \(0 < x < wx\)), then every beam fired from \((0,0)\) will hit that platform. In this case, only the first fired beam can trigger the chain reaction. Therefore, you should choose the launcher with the maximum energy to fire first. (The remaining fired launchers, though required, will be subsequently wasted.)
2. If no such platform exists, then every initial beam will travel directly to the enemy spaceship if the spaceship’s \(y\)-coordinate at \(x=wx\) (which is \(wx\) for a northeast beam) lies within \([sy, ty]\). In that case, the damage is simply the sum of the energies of the chosen \(k\) launchers. Otherwise, if the spaceship is not hit, the damage is 0.

Compute and output the maximum total damage that can be delivered to the enemy spaceship.

Note: Be sure to use LaTeX format for any formulas.

inputFormat

The input consists of multiple lines:

• The first line contains six integers: \(m\), \(k\), \(n\), \(wx\), \(sy\), \(ty\) where \(1 \le k \le m\); \(m\) is the number of available \(\alpha\) launchers on the initial platform; \(k\) is the number of launchers you must fire in order; \(n\) is the number of floating platforms; \(wx\) (\(wx>0\)) is the \(x\)-coordinate of the enemy spaceship; and \(sy, ty\) (with \(sy \le ty\)) represent the vertical span of the enemy spaceship.
• The second line contains \(m\) integers, the energy values of the available initial \(\alpha\) launchers. All these launchers fire in the northeast direction.
• Then follow \(n\) lines. Each of these lines contains: x y type pos v, where \(x\) and \(y\) are the coordinates of the floating platform, type is either A (for an \(\alpha\) launcher) or B (for a \(\beta\) launcher). If type is A, then pos is either upper or lower (specifying the firing direction: upper means northeast, lower means southeast). If type is B, the pos field can be a dash (-) and should be ignored. The integer \(v\) is the energy that the platform provides when activated.

It is guaranteed that all coordinates are integers. For a beam fired in the northeast direction from a point \((s_x,s_y)\), it will hit a platform at \((x,y)\) if and only if \(x > s_x\), \(y > s_y\), and \(x-s_x=y-s_y\). Similarly, a beam fired in the southeast direction from \((s_x,s_y)\) will hit a platform at \((x,y)\) if and only if \(x > s_x\), \(y<s_y\), and \(x-s_x=s_y-y\). The beam also hits the enemy spaceship when it reaches \(x=wx\) and the corresponding \(y\) coordinate is in \([sy,ty]\).

outputFormat

Output a single integer representing the maximum total damage that can be inflicted on the enemy spaceship.

sample

3 2 2 10 5 15
5 3 10
2 2 A upper 4
5 5 B - 6

20