#P9784. 搭房子

    ID: 6408 传统题 2000ms 256MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>CF2200提高+/省选-离散化三元环计数按度数定向时间戳避免清空数组高精度乘法

搭房子

题目描述

有 nn 块厚度可以忽略的矩形积木,第 ii 块的边长为 ai,bia_i,b_i。可以交换一块积木的长和宽。

选出恰好六块积木组成一个长方体。长方体的每个面恰好用一块积木,且积木的两条边长必须与该面的边长相等。每块积木最多使用一次。

求能组成的长方体的最大体积。若无法组成长方体,输出 −1-1。

输入格式

第一行一个整数 nn。接下来 nn 行,每行两个正整数 ai,bia_i,b_i,表示一块积木的边长。

输出格式

输出一行一个整数,表示最大体积或 −1-1。

样例

6
3 6
6 9
9 3
6 3
3 9
9 6
162

数据范围

6≤n≤2000006\le n\le200000。原题只给出了积木数量的上限。

原赛子任务 nn 上限 原赛分值 原赛依赖
1 500500 27 无
2 1000010000 36 1
3 200000200000 37 2

原 PDF 题面