PEG Judge - Spirits

PEG Test – Oct 3rd, 2014

Problem E: Spirits

Due to the harmonic convergence, spirits are leaking out from the spirit world. Some spirits are represented by Raava, the spirit of peace and light, so they are kind and friendly; other dark spirits are corrupted by Vaatu, the spirit of chaos and darkness, and are in turn devious and destructive.

Avatar Korra and her uncle Unalaq are having a duel in the spirit world, where light and dark spirits are entering the spirit world through the spirit portals at the north and south poles. The spirit world can be represented as a number line segment of length X, that is, there are X (5 ≤ X ≤ 1000) positions on the number line labeled from 1 to X. At position 1, is the spirit portal leading out to the north pole physical world, and at position X is the spirit portal leading out to the south pole of the physical world. Korra stands at position 1 and Unalaq stands at position X, deploying their spirits.

Korra sends out one light spirit every A seconds towards Unalaq, and Unalaq sends out one dark spirit every B seconds towards Korra (1 ≤ A, B ≤ 100). Korra has N (1 ≤ N ≤ 1000) light spirits lined up, numbered from 1 to N. Unalaq has M (1 ≤ M ≤ 1000) spirits lined up, numbered from 1 to M. Light spirit i has a strength of L_i and dark spirit i has a strength of D_i. All spirits move at a rate of 1 unit per second towards the opponent. If a light spirit every encounters a dark spirit (i.e. during the same second they occupy the same position, or they switch positions), then the stronger spirit will immediately consume the weaker spirit. If they are both equally as strong, then the dark spirit will prevail due to the impartiality of the convergence.

At the start, Korra and Unalaq will simultaneously deploy their first spirit (light spirit 1 and dark spirit 1, respectively) at the opposite portals. Light and dark spirits spawning will instantly appear at positions 1 and X, respectively. When a light spirit reaches position X, they will instantly exit the spirit world (unless of course, a dark spirit of greater or equal strength happens to spawn at X during that exact moment, in which case the light spirit will be consumed and not be able to exit the portal), and vice versa. Help Korra count how many light and dark spirits will reach and exit through the opposite portals after all of their spirits have been depleted.

Input Format

Line 1: The integers X, A, B, N, and M.
Line 2: N integers, L₁, L₂, …, L_N, representing the strengths of the light spirits.
Line 3: M integers, D₁, D₂, …, D_M, representing the strengths of the dark spirits.

Output Format

Two space-separated integers. The first represents the number of light spirits that reaches Unalaq's portal (position X) and can exit. The second represents the number of dark spirits that reaches Korra's portal (position 1) and can exit.