## Hoarder and Two Boxes

View as PDF

Points: 1
Time limit: 1.0s
Memory limit: 256M

Problem types

A hoarder named Aslı has a room in her house in the shape of a rectangular prism $$a$$ x $$b$$ x $$c$$ where she loves to hoard useless stuff in.

Aslı wants to pick up boxes of useless items from a flea market where there is a selection of $$n$$ boxes, and pile them in her hoarding room. Every box is in the form of a rectangular prism with dimensions $$x_i, y_i, z_i$$. Every box is placed in the room so that their surfaces are parallel to walls (boxes may be rotated $$90^o$$ in the directions of $$i$$, $$j$$, $$k$$).

Aslı can only carry two boxes home, and she wants to get the most amount of useless stuff in her house (volume-wise). She will take two boxes and put them in her hoarding room. Boxes can touch sides but cannot overlap, they also cannot be inside one another. The total volume occupied by these two boxes should be the maximum possible. What is the largest volume that can be occupied by the two boxes?

Input

The first line contains four integer numbers $$n, a, b$$ and $$c$$ $$(1 \leq n, a, b, c \leq 100)$$

Each of the next n lines contain three numbers $$x_i, y_i, z_i$$ $$(1 \leq x_i, y_i, z_i \leq 100)$$

Output

Print the largest total volume that can be occupied by two boxes. If you can not select two boxes, print 0.

Examples

Input(stdin)

3 6 3 2
3 2 3
3 2 1
3 2 2

Output(stdout)

30