Time Limit: Java: 2000 ms / Others: 2000 ms
Memory Limit: Java: 65536 KB / Others: 65536 KB
Suppose your windowing software only allows windows to be resized in such a way that their aspect ratios are unmodified. For example, a window with a width of 150 pixels and a height of 100 pixels (and an espect ratio of 150/100, or 1.5) can be resized so its width is 225 pixels and its height is 150 pixels (the aspect ratio remains unchanged, at 225/150, or 1.5), but a width of 224 and a height of 150 is not allowed, since that would change the aspect ratio. Each window can be moved to an arbitrary location on the screen, but the entire window must remain visible on the screen.
Given the size of a screen and the initial sizes of four different windows (as integer values for width and height), is it possible to resize (and relocate) the four windows so they completely cover the screen without overlapping each other? That's the question you are to answer in this problem.
For example, consider a square screen with four square windows. The aspect ratio for each of these is exactly 1. We are permitted to resize each of the four windows so they would completely fill the screen without overlapping. This case is illustrated by the first data set in the Sample Input, below.
400 400 10 10 35 35 15 15 100 100 200 300 10 10 20 20 30 45 40 60 200 250 10 10 20 20 30 45 40 60 0 0