Flappy Bird Score Maximization

In this problem, you are given (N) line segments that are axis‐parallel (either horizontal or vertical) in a 2D plane. The (i)-th segment ((0 \le i \le N-1)) has a weight (A_i) and endpoints ((X_{1,i}, Y_{1,i})) and ((X_{2,i}, Y_{2,i})).

Anna starts her flight from some point on the line (x=0) within the boundary (0 \le y \le H) and flies in the positive (x) direction until reaching the line (x=W). For safety reasons, her flight must always remain within the rectangular region (0 \le x \le W,; 0 \le y \le H).

Since Anna can only fly horizontally, her default flight path is a straight horizontal line. However, she is allowed to change her (y) coordinate exactly once during the flight by performing a vertical move (either upward or downward) at some (x=v), provided that her (x) coordinate remains unchanged during that vertical move. Thus, her flight path consists of two horizontal segments (at (y=y_1) and (y=y_2)) and one vertical segment at (x=v) connecting them. (If (y_1 = y_2), then no vertical move is used.)

Whenever Anna’s flight path shares at least one point with a segment, she earns that segment’s weight. Note that each segment’s weight is only added once, even if the flight path touches it more than once.

Formally, if Anna chooses an initial (y) coordinate (y_1) at (x=0), performs a vertical move at (x=v) to change her (y) coordinate to (y_2), and then continues horizontally to (x=W), her flight path is defined as: [ (0, y_1) \to (v, y_1) \to (v, y_2) \to (W, y_2). ]

Your task is to implement the function get_max_score that computes the maximum total score Anna can achieve by optimally choosing her starting (y) coordinate, her vertical move position (v) (if any), and her new (y) coordinate.

The function signature is provided as follows (using appropriate types for each language):

long long get_max_score(int W, int H, vector<int> A, vector<int> X1, vector<int> Y1, vector<int> X2, vector<int> Y2);

Note: There is no input/output in your submitted code; only implement the function.

inputFormat

The input is given in the following format (for testing purposes):

W H N
A[0] A[1] ... A[N-1]
X1[0] X1[1] ... X1[N-1]
Y1[0] Y1[1] ... Y1[N-1]
X2[0] X2[1] ... X2[N-1]
Y2[0] Y2[1] ... Y2[N-1]

where (W) and (H) are the boundaries of the flight in the (x) and (y) directions respectively, and (N) is the number of segments. The arrays A, X1, Y1, X2, Y2 each have (N) elements.

outputFormat

Output a single integer — the maximum score that Anna can achieve.

sample

5 4 3
10 -5 3
1 0 3
2 3 1
4 5 3
2 2 3

13