Custom Glasses Box Optimization

Little Hua bought an interesting magical glasses case. The lid of the case is made of two halves. Each half is horizontally divided into several strips of paper (see Figure 1), with the left half corresponding to the bottom and the right half to the top. The gray parts indicate the box surfaces and the white parts are blank regions. In some cases the box may have 3 strips (each of length 50 mm), but in general the number of strips and the lengths of the strips may vary.

The unique feature of the glasses box is that it can be folded in two different ways. In folding method 1 (see Figure 1(a)) the regions numbered 1, 2, …, n are exposed on the surface, and in folding method 2 (see Figure 1(b)) the regions numbered n+1, n+2, …, 2n are exposed. The region i and region n+i are congruent. You do not need to study how the two folding methods transform into each other in this problem.

Little Hua has two types of square paper pieces: formula pieces and cartoon pieces. She wants to paste the formula pieces on regions 1, 2, 3 (used in studying with folding method 1) and the cartoon pieces on regions 4, 5, 6 (used in resting with folding method 2). Each paper piece must be completely inside a region (their borders may coincide), and different pieces must be pasted on different regions. It is allowed that some regions have no paper pasted.

In the standard glasses box the overall dimensions are length 150 and width 55 so that the area is 8250. The case is divided into three equal-length strips, and therefore each white region has dimensions 55 × 50. Little Hua owns 3 formula pieces with side lengths 40, 45, and 52, and 4 cartoon pieces with side lengths 10, 27, 30, and 55. However, note that only the formula pieces with side lengths 40 and 45 can be used on the front (formula side) and only the cartoon pieces with side lengths 10, 27 and 30 can be used on the back. (Thus, the 52 and 55 pieces cannot be pasted.) Clearly the standard box cannot meet her requirements.

Luckily, the glasses box company accepts custom orders. One may choose the overall box dimensions (length and width), the number of paper strips, and the length of each strip arbitrarily. In other words, the box length need not be 150 nor the width 55. For example, Little Hua discovered that if one keeps the overall dimensions unchanged but replaces the strips with ones of lengths 40, 45, 55, and 10 (in order), then all the desired paper pieces can be pasted (see Figure 2).

Since a larger area means a more expensive box, Little Hua wishes to buy a box whose area does not exceed a given value \( s \). She wants to design the box (choose the box dimensions, the number and lengths of the strips) and decide on the pasting so that the total number of paper pieces pasted is maximized. Under the condition of pasting as many pieces as possible, what is the minimum area of a glasses box that can be produced?

Note: A region (formed by a strip) has dimensions \(W\) (the common width of the box) and \(L_i\) (the length of the \(i\)-th strip). A square paper piece of side \(a\) can be pasted into a region if \(a \le W\) and \(a \le L_i\) (its borders may coincide with those of the region). For a design in which a paper piece is pasted on a region, choose the region dimensions exactly equal to the paper side (to minimize area). Since the two halves of the lid are congruent, the same strip design is used for both sides. If a paper piece is pasted in both the front and back of the same strip then the strip must have length at least the maximum of the two piece’s side lengths. The overall box area is \(A = W \times (L_1+L_2+\cdots+L_n)\), and it must not exceed \(s\).

Usable pieces:

• Formula pieces (to be pasted on the front): only the pieces with side lengths 40 and 45 can be used.
• Cartoon pieces (to be pasted on the back): only the pieces with side lengths 10, 27 and 30 can be used.

You are to choose nonnegative numbers \(f\) and \(b\) (with \(f \le 2\) and \(b \le 3\)) indicating how many formula and cartoon pieces to paste. The box design must then consist of \(n\) strips where \(n \ge \max(f,b)\). You can assign at most one paper in each region, but you are free to pair a formula and a cartoon piece on the same strip. If a strip has a formula piece of side \(a\) and a cartoon piece of side \(b\) pasted on it, then its required length is \(\max(a,b)\). For strips with only one pasted piece, the strip’s length must be at least the piece’s side length. In an optimal design for a given selection of pieces, choose \(W\) equal to \(\max(maximum\ formula\ side, maximum\ cartoon\ side)\) and choose each used strip’s length equal to the minimum required for that strip. Unused strips can have arbitrarily small length. The minimum total area for a design is then \(A = W \times \Big(\sum_{\text{used strips}} required\ length\Big)\).

Given the maximum allowed box area \(s\), determine two numbers:

1. The maximum total number of paper pieces that can be pasted (i.e. \(f+b\)).
2. Under that maximum, the minimum achievable area \(A\) of the glasses box.

It is guaranteed that all input values are integers and that an optimal design with integer area exists.

inputFormat

The input consists of a single integer \(s\) (1 \(\le s \le 10^9\)) representing the maximum allowed area of the glasses box.

outputFormat

Output two integers separated by a space: the maximum number of paper pieces that can be pasted, and the minimum area among all designs achieving that number of pieces (the area will not exceed \(s\)).

Explanation: If no paper piece can be pasted, output 0 0.

sample

100

1 100