Song of Equipment Challenge

This problem is inspired by a story from zxy and the song chosen by gu gu. In this challenge, you have a character with two attributes: strength and spirit. The character has n pieces of equipment. For each equipment \(i\) (1-indexed), you are given nonnegative integers \(a_i\), \(b_i\), \(c_i\), and \(d_i\). To wear the \(i\)-th equipment, the character's current strength must be at least \(a_i\) and current spirit at least \(b_i\). Once worn, the equipment increases the character's strength by \(c_i\) and spirit by \(d_i\>.

You can choose the order in which to wear the equipment arbitrarily, as long as the corresponding conditions are met at the time of equipping. Your task is to determine the minimum initial strength \(S_0\) (a nonnegative integer) required so that with a suitable order there exists a way to wear all equipment. Under that minimum \(S_0\), you must also find the minimum initial spirit \(P_0\) (a nonnegative integer) required.

Input constraints and notes: It is guaranteed that if a solution exists, then both \(S_0\) and \(P_0\) are nonnegative integers. All formulas are written in \(\LaTeX\) format.

inputFormat

The first line contains a single integer \(n\) representing the number of equipment.

Each of the next \(n\) lines contains four space-separated integers \(a_i\), \(b_i\), \(c_i\), and \(d_i\) representing the requirements and the corresponding attribute increases for the \(i\)-th equipment.

outputFormat

Output two space‐separated nonnegative integers: the minimum initial strength \(S_0\) and, under that, the minimum initial spirit \(P_0\) required to wear all equipment in some order.

sample

1
5 5 1 1

5 5