Flappy Bird Challenge

Flappy Bird is a popular casual mobile game. In this problem, the game rules have been simplified and modified. The game interface is a 2D plane with width \(n\) and height \(m\), and there are \(k\) pipes (the width of each pipe is negligible). The bird starts at \(x=0\) at any integer height in the range \([1, m]\) and moves to \(x=n\) to finish the game. At each unit time, the bird automatically moves one unit to the right. At the same time, the player can control the vertical movement. Specifically, at the current column the bird is at, if the player clicks the screen, the bird ascends; multiple clicks in one time unit are allowed and their effects are additive. If the player does not click the screen in that time unit, the bird descends.

For each move (from column \(i-1\) to column \(i\), \(1 \le i \le n\)), two parameters are given:

• \(U_i\): the vertical distance the bird ascends per click (if the player clicks at least once). Note that if the bird is already at height \(m\), it cannot ascend.
• \(D_i\): the vertical distance the bird descends if the player does not click at all.

That is, for each move \(i\), the player can choose a nonnegative integer number of clicks \(f\). If \(f \ge 1\), the bird's height increases by \(f \times U_i\); if \(f=0\), the bird's height decreases by \(D_i\). In all cases the bird’s new height must remain in the interval \((0, m]\) (if it becomes \(0\) the game fails).

In addition, there are \(k\) pipes located at specified columns. Each pipe is given by three integers \(p, L, R\) (with \(1 \le p \le n-1\)). When the bird is at column \(p\), it must be within the safe gap of the pipe; that is, its height \(h\) must satisfy \(L < h < R\) (using < in strict sense, so touching the boundary counts as collision).

The task is as follows: Determine if it is possible for the bird to reach \(x=n\) without failing. If it is possible, output the minimum total number of screen clicks required. Otherwise, output the maximum number of pipes the bird can pass (i.e. the maximum count of pipes for which the bird’s height satisfies the safe gap condition) before failure.

Note: The upward and downward distances \(U_i\) and \(D_i\) may vary for different moves.

inputFormat

The input consists of several lines:

1. The first line contains three integers \(n\), \(m\) and \(k\) separated by spaces.
2. The second line contains \(n\) integers: \(U_1, U_2, \dots, U_n\), where \(U_i\) is the upward distance per click at move \(i\).
3. The third line contains \(n\) integers: \(D_1, D_2, \dots, D_n\), where \(D_i\) is the downward distance if no click occurs at move \(i\).
4. Each of the following \(k\) lines contains three integers \(p\), \(L\) and \(R\) describing a pipe located at column \(p\) (with \(1 \le p \le n-1\)) having a safe gap \((L, R)\) (i.e. the bird is safe if \(L < h < R\) at that column).

outputFormat

Output a single integer. If it is possible for the bird to reach \(x=n\) safely, output the minimum total number of screen clicks required. Otherwise, output the maximum number of pipes that the bird can successfully pass.

sample

3 10 1
2 3 2
1 2 1
2 3 8

1