Domácí kolo

H: Nejvyšší dort

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Soutež skončila. Získané body již nejdou do výsledků.

Zadání (Řešení)

Organizátoři Kasiopey pečou dort pro nejlepšího programátora. Jednotlivé díly dortu připravují v různých formách a přemýšlejí, jak je naskládat na sebe, aby byl dort co nejvyšší, ale aby zároveň nespadl.

Máme N forem na korpus ve tvaru kvádrů. Všechny formy jsou stejně dlouhé, důležitá je pro nás tedy pouze jejich šířka a výška. Upečený díl dortu tedy buď umístíme tak, jak jsme ho vyklopili z formy, nebo ho můžeme otočit na stranu o 90 stupňů (a pak bude tak široký, jak byla jeho forma vysoká a naopak). Aby byl dort stabilní, musí být horizontální šířka každého dílu dortu ostře menší než šířka dílu pod ním. Jak vysoký dort můžeme vytvořit za předpokladu, že musíte použít všechny díly?

Můžete předpokládat, že existuje způsob, jak dort postavit se všemi N díly dortu.

Tvar vstupu

Na prvním řádku se nachází počet testovacích vstupů T.

Pro každý testovací vstup se na prvním řádku nachází samostatně číslo N udávající počet forem. Následuje N řádků s dvěma čísly Si, Vi oddělenými mezerou, které udávají šírku a výšku i-té formy.

Tvar výstupu

Pro každý testový vstup vypište na samostatný řádek výšku nejvyššího dortu.

Lehká verze

  • T ≤ 15
  • 1 ≤ Si ≤ Vi ≤ 109
  • N ≤ 10 000

Těžká verze

  • T ≤ 15
  • 1 ≤ Si ≤ Vi ≤ 109
  • N ≤ 200 000

Ukázkový vstup

2
1
1000 1000
3
50000 160000
50000 100000
50000 100000

Ukázkový výstup

1000
200000

Vysvětlení ukázkového vstupu a výstupu

V prvním případě je forma stejně široká i hluboká a dort se skládá jen z jednoho dílu, lze tedy postavit pouze jedním způsobem.

V druhém případě vidíme, že máme na výběr pouze ze třech různých hodnot výšek a šířek formy. Jelikož musíme pokládat každý díl na ostře širší, získáváme tak už výsledné rozměry jednotlivých dílů. Nejprve použijeme otočený díl z první formy s šířkou 160 000 a výškou 50 000, na něj položíme otočený díl z druhé formy s šířkou 100 000 a výškou 50 000 a nakonec neotočený díl z třetí formy s šířkou 50 000 a výškou 100 000.

Pracujete-li v jazyce typu C++, důrazně doporučujeme použít na uchování výsledku proměnnou typu long long (alespoň 64 bitů).

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)