open System
open System.Collections.Generic

module InputUtility =
    let InputTokens = new Queue<string>()

    let EnsureInput () =
        if InputTokens.Count = 0 then
            let input = Console.ReadLine ()
            let s = input.Split ([|' '|], StringSplitOptions.RemoveEmptyEntries)
            if s.Length > 0 then
                for x in s do InputTokens.Enqueue(x)
                true
            else false
        else true

    let rec ReadNext () =
        if EnsureInput () then InputTokens.Dequeue ()
        else ReadNext ()

    let ReadNextInt () = ReadNext () |> int

    let Read2Int () = ReadNextInt (), ReadNextInt ()

    let ReadListOf f n =
        let rec loop acc = function
            | 0 -> List.rev acc
            | c -> loop ((ReadNext () |> f) :: acc) (c-1)
        loop [] n

    let MultipleCaseWithId f =
        let caseNum = ReadNextInt ()
        let rec loop index =
            if index = caseNum then ()
            else
                f index
                loop (index + 1)
        loop 0

    let MultipleCase f = MultipleCaseWithId (fun _ -> f ())

open InputUtility

module ARC074 =
    type 'a PriorityQueue (cmp, ?initSize) =
        let mutable size = 0
        let mutable a = Array.zeroCreate<'a> (match initSize with | Some v -> v | _ -> 128)
        let rec sink u x =
            let y = x * 2
            if y <= size then
                let z = if y < size && cmp a.[y + 1] a.[y] then y + 1 else y
                if cmp a.[z] u then
                    a.[x] <- a.[z]
                    sink u z
                else a.[x] <- u
            else a.[x] <- u
        let rec swim v y =
            let x = y / 2
            if x > 0 && cmp v a.[x] then
                a.[y] <- a.[x]
                swim v x
            else a.[y] <- v
        let throwIfEmpty () =
            if size = 0 then failwith "empty priority queue node"
        member p.Count with get () = size
        member p.Top with get () = throwIfEmpty (); a.[1]
        member p.Push v =
            if size + 1 = a.Length then
                let na = a.Length * 2 |> Array.zeroCreate
                for i in [1..size] do na.[i] <- a.[i]
                a <- na
            size <- size + 1
            swim v size
        member p.Pop () =
            throwIfEmpty ()
            let r = a.[1]
            size <- size - 1
            sink a.[size + 1] 1
            r

        override p.ToString () =
            System.String.Join (" ", a |> Seq.skip 1 |> Seq.take size)
            |> sprintf "%s"

    let private ``3N Numbers`` () =
        let n = ReadNextInt ()
        let un = 3 * n
        let a = ReadListOf int64 un |> Seq.toArray
        let rec gen (pq: _ PriorityQueue) (r: _ array) g d i s =
            if g i then
                pq.Push a.[i]
                //printfn "%d +%d: %A" i a.[i] pq
                let ds = if pq.Count > n then pq.Pop () else 0L
                let ns = s + a.[i] - ds
                r.[i] <- ns
                //printfn "%d: %A => %d | %d" i pq ns s
                gen pq r g d (i + d) ns
            else r
        let fp f = gen (new PriorityQueue<_> (f)) (Array.zeroCreate un)
        let g = fp (<) ((>) un) 1 0 0L
        let h = fp (>) ((<) -1) -1 (un - 1) 0L
        //printfn "%A\n%A" g h
        let rec loop i r =
            if i + n < un then
                let nr =
                    g.[i] - h.[i + 1]
                    |> max r
                loop (i + 1) nr
            else r
        loop (n - 1) System.Int64.MinValue |> printfn "%d"

    let Entry = ``3N Numbers``

ARC074.Entry ()

Measured memory_bytes: 60424