We are creating an arrangement of $$$3$$$ fake Christmas trees, equally-spaced along a line, for the backdrop of a play.
Each of the fake trees is made out of a vertical trunk and one or more identical triangular pieces of foam designed to be attached to that particular trunk. The pieces for tree $$$i$$$ all have exactly the same shape of an isosceles triangle with base width equal to double the height ($$$(2 \cdot s_i) \times (s_i)$$$ centimetres).
A tree trunk can have triangles attached at predefined attachment points defined in terms of the elevation from the base of the tree. To make the trees look as full of life as possible, in their foamy way, we want the sum of the areas of the pieces attached on the trees to be as large as possible.
However, the set of pieces we can actually install is limited because we do not want any of the triangles to overlap each other except for touching at the perimeter.
Find a subset of pieces to use with the maximum possible area, while still having none of the pieces on any of the trees overlap.
 |  |
Tree arrangements illustrating samples 1 and 2.
Find the maximum sum of areas of triangles that we can install.
- One line containing the integer distance between trees $$$A$$$ and $$$B$$$, and between $$$B$$$ and $$$C$$$ in centimetres, $$$d$$$ ($$$1 \leq d \leq 10^7$$$),
- Three descriptions of trees $$$A$$$, $$$B$$$, and $$$C$$$:
- One line containing the number of triangle positions $$$n_i$$$ and triangle size $$$s_i$$$ of the $$$i$$$-th tree. ($$$1 \le n \le 100$$$; $$$1 \le s \le d$$$).
- One line containing the $$$n_i$$$ possible integer triangle heights in centimetres, $$$y_{ij}$$$ ($$$0 \le y \le 10^7$$$).
Output the maximum possible combined area of triangular pieces on the trees.
53 11 3 63 23 1 03 40 2 4
43
53 20 1 23 40 2 43 20 1 2
40
