Problem description

Back
Show PDF
Mistrzostwa
(mis)
Limit pamięci: 256 MB
Limit czasu: 2.50 s

Wielkimi krokami zbliżają się Mistrzostwa Świata w Piłce Nożnej. Aby wyłonić absolutnie najlepszych z najlepszych, organizatorzy postanowili zorganizować w Bajtogrodzie prestiżowy, pokazowy Turniej Gwiazd. Wezmą w nim udział wyłącznie reprezentanci trzech krajów uznawanych za głównych faworytów do złota: Hiszpanii, Francji oraz Anglii.

Z każdego z tych państw na zgrupowanie w Bajtogrodzie przyjechało dokładnie N zawodników. Każdy piłkarz został szczegółowo przebadany, a jego aktualną formę opisano za pomocą współczynnika siły. Zawodnicy z Hiszpanii mają siły opisane ciągiem A = (A1,A2,…,AN), z Francji ciągiem B = (B1,B2,…,BN), natomiast z Anglii – ciągiem C = (C1,C2,…,CN).

Selekcjonerem gospodarzy został legendarny Bajtazar. Jego zadaniem jest stworzenie trzyosobowej drużyny marzeń. Zasady rekrutacji są jednak rygorystyczne: W skład każdej drużyny musi wejść dokładnie jeden gracz z Hiszpanii, jeden z Francji oraz jeden z Anglii. Ponieważ jest to turniej pokazowy, różni selekcjonerzy mogą powoływać tych samych zawodników, jednak żadne dwa zespoły nie mogą mieć identycznego składu. Oznacza to, że każda drużyna jest jednoznacznie wyznaczona przez trójkę indeksów (i, j, k).

Analitycy Bajtazara odkryli, że z powodu specyfiki taktycznej, całkowita siła drużyny składającej się z zawodników o siłach Ai, Bj oraz Ck wyraża się specjalnym, “synergicznym” wzorem: AiBj + BjCk + CkAi.

Wybór drużyn odbywa się w systemie kolejkowym. Przed Bajtazarem swoje składy zarejestrowało już K − 1 innych trenerów. Każdy z nich wybierał drużynę o absolutnie największej możliwej sile spośród jeszcze dostępnych kombinacji.

Bajtazar podchodzi do stolika sędziowskiego jako K-ty w kolejce. Pomóż utytułowanemu selekcjonerowi i oblicz, jaką maksymalną siłę będzie miała drużyna, którą przyjdzie mu sformować.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N oraz K. W drugim wierszu znajduje się N liczb całkowitych A1, A2, …, AN. W trzecim wierszu znajduje się N liczb całkowitych B1, B2, …, BN. W czwartym wierszu znajduje się N liczb całkowitych C1, C2, …, CN.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – maksymalna siła drużyny Bajtazara.

Ograniczenia

1 ≤ N ≤ 2 ⋅ 105, 1 ≤ K ≤ min (N 3,5⋅105), 1 ≤ Ai, Bj, Ck ≤ 109.

Podzadania

Podzadanie Warunki Punkty
1 N ≤ 200 15
2 N ≤ 2000, K ≤ 50 15
3 Ck = 1 dla każdego k 30
4 brak dodatkowych ograniczeń 40

Przykład

Wejście Wyjście Wyjaśnienie 
2 5
1 2
3 4
5 6

31

Wartości dla 8 możliwych wyborów drużyn są obliczane następująco:

  • Dla (i = 1, j = 1, k = 1): 1 ⋅ 3 + 3 ⋅ 5 + 5 ⋅ 1 = 23
  • Dla (i = 1, j = 1, k = 2): 1 ⋅ 3 + 3 ⋅ 6 + 6 ⋅ 1 = 27
  • Dla (i = 1, j = 2, k = 1): 1 ⋅ 4 + 4 ⋅ 5 + 5 ⋅ 1 = 29
  • Dla (i = 1, j = 2, k = 2): 1 ⋅ 4 + 4 ⋅ 6 + 6 ⋅ 1 = 34
  • Dla (i = 2, j = 1, k = 1): 2 ⋅ 3 + 3 ⋅ 5 + 5 ⋅ 2 = 31
  • Dla (i = 2, j = 1, k = 2): 2 ⋅ 3 + 3 ⋅ 6 + 6 ⋅ 2 = 36
  • Dla (i = 2, j = 2, k = 1): 2 ⋅ 4 + 4 ⋅ 5 + 5 ⋅ 2 = 38
  • Dla (i = 2, j = 2, k = 2): 2 ⋅ 4 + 4 ⋅ 6 + 6 ⋅ 2 = 44

Sortując te siły zespołów malejąco, otrzymujemy kolejno: (44,38,36,34,31,29,27,23). Piąta największa siła, czyli ta która należy do drużyny Bajtazara, to właśnie 31.
Wejście Wyjście 
3 10
100 100 100
100 100 100
100 100 100

30000
Wejście Wyjście 
5 54
800516877 573289179 26509423 168629803 696409999
656737335 915059758 201458890 931198638 185928366
140174496 254538849 830992027 305186313 322164559

689589940713840351