Time limit per test: 0.25
Memory limit: 65536
lemmings appear in the point A
) one after another with interval of s
seconds. Lemmings always go forward, they can't go backward, but can change their direction. Lemmings are not really smart and always use the same algorithm: they either drop down with velocity 1 cm/sec, if they do not touch a platform, or walk on the platform forward with velocity 1 cm/sec, until reaching the end of the platform (platforms are the horizontal segments that do not intersect, do not collide and do not touch each other). Newly appeared lemming has direction to the right (thus, to the positive direction of x-axis). Lemming may finish its movement either in infinite falling down or at the home located at the point (a
) on some platform. Reaching home is ultimate goal for each lemming.
You need to maximize amount of lemmings that reach home, and to minimize time when the last lemming reaches home. You may perform only one action: choose any lemming that is moving by the platform now (or have just fallen down to the platform), and stop it. If the lemming was stopped it will stay at its place forever, and all lemmings touched it (either dropped or came from either side) will reverse their direction. Point A
doesn't touch any platform.
The first line of the input file contains two integer numbers N
(1 ≤ N
≤ 100; 1 ≤ s
≤ 10). Next line contains four numbers x
- coordinates of the point A
and of the home (0 ≤ x
≤ 10000). Third line contains the number of platforms M
(1 ≤ M
≤ 100). Next M
lines describe platforms. Platform description consists of three numbers l
, where (l
) is the left end of the platform and (r
) is the right end of the platform (0 ≤ l
≤ 10000; l
). It is guaranteed that after falling from any platform lemming either infinitely falling or falls to the inner point of some platform. All numbers in the input file are integer.
Print two integer numbers in the output file: K
- maximal possible number of lemmings reached the home, and T
- minimal time of reaching the home of the last lemming. First lemming appears at the 0 time moment. If no one lemming can reach the home, print 0 0.
Notes to the example
6 5 6 0
1 2 4
4 7 4
3 5 2
0 6 0
It is necessary to stop first two lemmings at points (6, 4) and (4, 2) respectively.