Speeding Vehicle Detection on a National Road

A national road of length \(L\) is monitored by \(m\) speed detectors placed at positions \(p_j\) (measured from the south end). There are \(n\) vehicles entering the road. The \(i\)th vehicle enters the road at position \(d_i\) with an initial speed \(v_i\) and accelerates uniformly with acceleration \(a_i\) (which may be positive, zero, or negative). Note that \(v_i > 0\). Each vehicle drives northward until it either reaches the north end (at position \(L\)) or, if \(a_i<0\), its speed decreases to \(0\), in which case it is considered to have left the road.

Every speed detector can be turned on or off. When a vehicle passes an active detector, if its instantaneous speed exceeds the road speed limit \(V\) (i.e. is \(>V\)), then it is marked as speeding. This applies both when vehicles enter and exit the road. (A vehicle passes a detector if the detector is located at the exact position where it enters or leaves the road.)

Your tasks are:

1. Assuming all detectors are turned on, determine how many vehicles are marked as speeding.
2. For energy saving, the department wishes to turn off as many detectors as possible while ensuring that every vehicle that was marked as speeding when all detectors were on will still be marked as speeding by at least one active detector. Find the maximum number of detectors that can be turned off.

Hint on Kinematics: For uniform acceleration, the relation between speed and displacement is given by \[ v^2 = v_0^2 + 2a (s - s_0). \] This formula may help you determine the speed of a vehicle at any position \(s\) on the road.

Note: When formulating the conditions for speeding, if a vehicle's instantaneous speed equals \(V\) at a detector, it is not considered to be speeding; it must be strictly greater than \(V\).

inputFormat

The first line of input contains four numbers: \(L\) \(V\) \(n\) \(m\), where \(L\) (a positive integer) is the length of the road, \(V\) (a positive integer) is the speed limit, \(n\) is the number of vehicles, and \(m\) is the number of speed detectors.

The following \(n\) lines each contain three numbers: \(d_i\), \(v_i\), and \(a_i\). Here, \(d_i\) (an integer) denotes the position where the \(i\)th vehicle enters the road, \(v_i\) (a positive integer) is its initial speed, and \(a_i\) (an integer that may be negative, zero, or positive) is its acceleration.

The last line contains \(m\) integers representing the positions of the speed detectors: \(p_1, p_2, \dots, p_m\). The positions are given in increasing order (not necessarily, your solution should sort them as needed).

outputFormat

Output two integers separated by a space. The first integer is the number of vehicles marked as speeding when all detectors are active. The second integer is the maximum number of detectors that can be turned off while ensuring that every speeding vehicle (under full detection) is still detected by at least one active detector.

sample

100 60 3 5
0 50 10
20 80 0
50 100 -10
10 55 70 90 100

3 4