Alice has a dartboard consisting of $$$N$$$ concentric convex polygons numbered from $$$1$$$ to $$$N$$$ (from innermost to outermost). Each polygon $$$i$$$ has a score $$$S_i$$$ and is given by its vertices in the plane. When a dart lands on the dartboard, its score is $$$S_i$$$, where $$$i$$$ is the smallest index such that the dart lies inside polygon $$$i$$$. In other words, if a dart lies inside multiple polygons, the innermost one determines the score.
Alice throws $$$M$$$ darts in total:
- For $$$K$$$ darts (precision mode), Alice chooses a polygon $$$t$$$. The dart lands uniformly at random inside polygon $$$t$$$.
- For the remaining $$$(M-K)$$$ darts, each dart lands uniformly at random inside the outermost polygon.
Alice wants to maximize her expected total score. Find this maximum expected score. Since the answer is a rational number $$$\frac{P}{Q}$$$, output it as $$$P \times Q^{-1} \pmod{10^9+7}$$$.
The first line contains three integers $$$N, M, K$$$ $$$(1 \le N \le 10^3, 1 \le M \le 10^3, 0 \le K \le M)$$$ — the number of polygons, total darts, and precision darts.
The second line contains $$$N$$$ integers $$$S_1, S_2, \ldots, S_N$$$ $$$(1 \le S_i \le 10^3)$$$ — the scores of the polygons.
Then for each polygon $$$i$$$ $$$(1 \le i \le N)$$$:
- The first line contains an integer $$$v_i$$$ $$$(3 \le v_i \le 10^3)$$$ — the number of vertices of polygon $$$i$$$.
- Each of the next $$$v_i$$$ lines contains two integers $$$x_j, y_j$$$ $$$(|x_j|, |y_j| \le 10^3)$$$ — the coordinates of the vertices in counterclockwise order.
It is guaranteed that polygons are concentric and strictly nested: polygon $$$i$$$ lies strictly inside polygon $$$i+1$$$.
Print a single integer — the maximum expected total score modulo $$$10^9+7$$$.
3 565 552 939 327 520 5 -475 -422 447 -175 731 54 -479 404 -811 23 7 -832 -272 191 -747 361 -548 927 310 264 739 -517 677 -866 -24 7 -864 -403 -447 -882 138 -873 983 284 929 969 -301 843 -934 374
600579066
