TH-TMO 2015 Problem 3

Let $P = \{(x, y) | x, y \in \{0, 1, 2,... , 2015\}\}$ be a set of points on the plane. Straight wires of unit length are placed to connect points in $P$ so that each piece of wire connects exactly two points in $P$ , and each point in $P$ is an endpoint of exactly one wire. Prove that no matter how the wires are placed, it is always possible to draw a straight line parallel to either the horizontal or vertical axis passing through midpoints of at least $506$ pieces of wire.