At last! Finally! AC - I've done it! My ultra-optimized program (15 kBytes) has passed all the tests (22 or more!) within 0.593 sec (maximal time on 8-th test with N=40). During almost a week I've been trying to solve it - and now success! I really think this problem is one of the best on Ural, and one of the several from thousands I really proud to solve - bright idea, need for strict optimization and very tricky tests (especially 16 and 22). Just try to solve it - and feel the power of your brain!

Yes, this problem is REALLY superior! I was forced to use __int64-calculations to avoid error in precision, so 0.921 sec. There is 10 tasks in one! #1271 is the best on Timus!