Arranging arbitrary rectangles to fill a space Can these rectangles fill a rectangular space?

Given a bunch of rectangles, you are asked whether or not they can be arranged to fill a rectangular space.

Specs

Given a bunch of arbitrary m x n rectangles; 0 &lt;= m, n &lt;= 1000, determine whether or not it is possible to arrange them so that they cover exactly a rectangular area without any holes or overlaps. The rectangles cannot be rotated, and each rectangle may only be placed once.

Input

The input for this is very flexible, as long as the input gives some sort of list of 2-space dimensions. For example, both of the following are valid:

Separated by Space, Return

1 2
1 5
4 5
3 6


List of Dimensions

[[1, 2], [1, 5], [4, 5], [3, 6]]

Output

Any sort of true/false values like true/false, 0/1, T/F, True/False, etc. If you are going to use an output method that's not very obvious, please specify in your answer.

Examples

Test Case 1

Input:

1 1
1 5
2 6


Output:
true (or something similar)
How to arrange it:

XYYYYY
ZZZZZZ
ZZZZZZ


Test Case 2 

Input:

1 1
2 2


Output:
false (or something similar)
Explanation: It becomes obvious that you cannot arrange two squares of different sizes and get their edges to line up.

Test Case 3

Input:

1 1
1 2
1 2
2 1
2 1


Output:
true (or something similar)
How to arrange it:

AAB
DEB
DCC


As @ETHProductions pointed out, for all of the other test cases, you can keep combining rectangles with a common edge length until you have only one rectangle, so this test case is just to break any code that uses this idea.

Test Case 4

Input:

3 2
4 1
2 1
4 1
2 1
5 2
3 2
1 4
3 2
2 1
2 1
1 1
5 1


Output:
true (or something similar)
How to arrange it:

AAABBBBEE
AAACCDDDD
FFFFFGGGH
FFFFFGGGH
IIIJJKKLH
IIIMMMMMH


Note: You do not need to state how to arrange it, you only need to determine whether not it can be arranged.

This is code golf, so the shortest answer in bytes wins! I will accept the shortest answer as of January 14th, but feel free to submit answers later than that since I can still give upvotes! :)

Happy golfing!

~ A.L.

P.S. If you know what tag should be applied to this problem, please add it, I have absolutely no idea what to put as a tag other than code-golf.

EDIT: Your program should be able to process up to 25 rectangles, in at most 10 seconds on a decent computer (I'll be quite flexible on this rule).

EDIT: I've extended the submission acceptance deadline to the last day of the year, but I doubt I'll get an answer by then...

EDIT: I've extended the submission acceptance deadline by 2 weeks, so if no more answers come in by then, the current C answer will be accepted! :)
Haskell, 226 bytes

((y,z):l)&amp;(w,x)|x*y&lt;1=(w+y,x+z):l
(q:l)&amp;p=p:q:l
(p@(u,v):r@(y,z):l)%q@(w,x)=[((y-w,z):l)&amp;q&amp;(u,v-x)|w&lt;=y,x&lt;=v]++[p:m|m&lt;-(r:l)%q]
_%_=[]
g m(p:n)l=any(g[]$m++n)(l%p)||g(p:m)n l
g[]_[_,_,_]=0&lt;1
g _[]_=0&lt;0
($[(0,9^9),(9^9,0)]).g[]


Try it on Ideone

How it works

This recursively searches for all partial tilings whose shape is a Young diagram, adding one rectangle at a time, and checks whether any of the final results are rectangles.

To see that any tiling of a rectangle can be built this way: in any tiling of a nonempty Young diagram, let R be the set of rectangles in the tiling whose southwest corner does not touch any other rectangle.  Since each concave vertex of the Young diagram is edge-adjacent (not merely corner-adjacent) to at most one rectangle in R, and the number of these concave vertices is one less than the number of rectangles in R, there must be at least one rectangle in R that is edge-adjacent to none of these concave vertices.  Removing it yields another Young diagram, so we can proceed by induction.