using System;

using System.Collections.Generic;

public class Program

{

    public static long kRectangleIntersection (int[] xl, int[] yl, int[] xh, int[] yh, int K)

    {

        int N = xl.Length;

        if ( K == 1 )

        {

            long mArea = 0L;

            for (int i = 0;i < N;i++)

            {                               

                BusyRectangle newRect = new BusyRectangle(xl[i], yl[i], xh[i], yh[i]);

                mArea = Math.Max (mArea, newRect.Area ());

            }

            return mArea;

        }

        Dictionary<BusyRectangle,HashSet<int>> hash = new Dictionary<BusyRectangle,HashSet<int>> ();

        for (int i = 0;i < N;i++)

        {

            for (int j = i + 1;j < N;j++)

            {

                int iXl = Math.Max (xl[i], xl[j]);

                int iYl = Math.Max (yl[i], yl[j]);

                int iXh = Math.Min (xh[i], xh[j]);

                int iYh = Math.Min (yh[i], yh[j]);

                if ( iXl < iXh && iYl < iYh )

                {

                    hash.Add(new BusyRectangle(iXl, iYl, iXh, iYh), new HashSet<int> ());

                }

            }

        }                       

        Dictionary<BusyRectangle,HashSet<int>> hash4 = new Dictionary<BusyRectangle,HashSet<int>> ();

        int power = 2;

        //while ( power < K )

        {

            var allKeys = new List<BusyRectangle> (hash.Keys);

            for (int i = 0;i < allKeys.Count;i++)

            {

                for (int j = i + 1;j < allKeys.Count;j++)

                {

                    int iXl = Math.Max (hash[allKeys[i]].xl, hash[allKeys[j]].xl);

                    int iYl = Math.Max (hash[allKeys[i]].yl, hash[allKeys[j]].yl);

                    int iXh = Math.Min (hash[allKeys[i]].xh, hash[allKeys[j]].xh);

                    int iYh = Math.Min (hash[allKeys[i]].yh, hash[allKeys[j]].yh);

                    if ( iXl < iXh && iYl < iYh )

                    {

                    }

                }

            }

            power <<= 1;

        }

        bool[] notIntersect = new bool[N];

        bool flag = false;

        for (int k=1;k < K && !flag;k++)

        {

            Console.WriteLine ("k: " + k + " Total rectangles: " + hash.Keys.Count);

            var allKeys = new List<BusyRectangle> (hash.Keys);

            long mArea = 0L;

            int maxCount = 0;

            //Dictionary<BusyRectangle,HashSet<int>> newHash = new Dictionary<BusyRectangle,HashSet<int>> ();

            int countNew = 0;

            for (int i = 0;i < N;i++)

            {

                if ( notIntersect[i] )

                    continue;

                bool bIntersect = false;                

                foreach (var key in allKeys)

                {

                    if ( hash[key].Contains (i) )//|| hash[key].Count < k )

                        continue;

                    int iXl = Math.Max (xl[i], key.xl);

                    int iYl = Math.Max (yl[i], key.yl);

                    int iXh = Math.Min (xh[i], key.xh);

                    int iYh = Math.Min (yh[i], key.yh);

                    if ( iXl < iXh && iYl < iYh )

                    {                                               

                        bIntersect = true;                                              

                        BusyRectangle newRect = new BusyRectangle(iXl, iYl, iXh, iYh);

                        //newHash.Add(newRect, );

                        mArea = Math.Max (mArea, newRect.Area());

                        if ( hash.ContainsKey (newRect) )

                        {

                            int prevCount = hash[newRect].Count;

                            //newHash.Add(newRect, new HashSet<int> (hash[newRect]));

                            //newHash[newRect].Add (i);

                            hash[newRect].Add (i);

                            hash[newRect].UnionWith (hash[key]);                            

                            if ( prevCount < hash[newRect].Count)

                                countNew++;

                        }

                        else

                        {

                            hash.Add (newRect, new HashSet<int>(new List<int> () {i}));

                            hash[newRect].UnionWith (hash[key]);

                            countNew++;

                        }       

                        maxCount = Math.Max (maxCount, hash[key].Count);

                    }

                }

                if ( !bIntersect || countNew == 0 )

                    notIntersect[i] = true;                             

                if ( countNew == 0 )

                {

                    flag = true;

                    break;

                }

                Console.WriteLine ("k: " + k + " i: " + i + " Total rectangles: " + hash.Keys.Count);

                all = new List<BusyRectangle> (hash.Keys);

                all.Sort ();

​

                foreach (var key in all)

                {

                    //Console.WriteLine ("Rect: " + key.ToString() + " count: " + hash[key].Count);

                }

            }

            //??? Possible optimization 

                List<BusyRectangle> removeKeys = new List<BusyRectangle> ();

                foreach (var key in hash.Keys)

                    if ( hash[key].Count <= (k + 1) )//maxCount )//|| key.Area () < mArea )

                        removeKeys.Add (key);

                Console.WriteLine ("Keys to remove: " + removeKeys.Count);

                foreach (var rect in removeKeys)

                    hash.Remove (rect);

                //hash = hash.Where(it => it.Value.Count == (k + 1)).ToDictionary(it => it.Key, it => it.Value);

                //???

                Console.WriteLine ("2 k: " + k + " Total rectangles: " + hash.Keys.Count);

        }

        long maxArea = 0L;

        foreach (var key in hash.Keys)

        {

            if ( hash[key].Count >= K )

            {

                maxArea = Math.Max (maxArea, key.Area());

            }

        }

        return maxArea;

    }

    /*public static long kRectangleIntersection (int[] xl, int[] yl, int[] xh, int[] yh, int K)

    {

        int N = xl.Length;

        Dictionary<BusyRectangle,HashSet<int>> hash = new Dictionary<BusyRectangle,HashSet<int>> ();

        for (int i = 0;i < N;i++)

        {

            BusyRectangle newRect = new BusyRectangle(xl[i], yl[i], xh[i], yh[i]);

            if ( hash.ContainsKey (newRect) )

            {

                hash[newRect].Add (i);

            }

            else

            {

                hash.Add (newRect, new HashSet<int>(new List<int> () {i}));

            }

        }

        bool[] notIntersect = new bool[N];

        bool flag = false;

        for (int k=1;k < K && !flag;k++)

        {

            Console.WriteLine ("k: " + k + " Total rectangles: " + hash.Keys.Count);

            var allKeys = new List<BusyRectangle> (hash.Keys);

            long mArea = 0L;

            int maxCount = 0;

            //Dictionary<BusyRectangle,HashSet<int>> newHash = new Dictionary<BusyRectangle,HashSet<int>> ();

            int countNew = 0;

            for (int i = 0;i < N;i++)

            {

                if ( notIntersect[i] )

                    continue;

                bool bIntersect = false;                

                foreach (var key in allKeys)

                {

                    if ( hash[key].Contains (i) )//|| hash[key].Count < k )

                        continue;

                    int iXl = Math.Max (xl[i], key.xl);

                    int iYl = Math.Max (yl[i], key.yl);

                    int iXh = Math.Min (xh[i], key.xh);

                    int iYh = Math.Min (yh[i], key.yh);

                    if ( iXl < iXh && iYl < iYh )

                    {                                               

                        bIntersect = true;                                              

                        BusyRectangle newRect = new BusyRectangle(iXl, iYl, iXh, iYh);

                        //newHash.Add(newRect, );

                        mArea = Math.Max (mArea, newRect.Area());

                        if ( hash.ContainsKey (newRect) )

                        {

                            int prevCount = hash[newRect].Count;

                            //newHash.Add(newRect, new HashSet<int> (hash[newRect]));

                            //newHash[newRect].Add (i);

                            hash[newRect].Add (i);

                            hash[newRect].UnionWith (hash[key]);                            

                            if ( prevCount < hash[newRect].Count)

                                countNew++;

                        }

                        else

                        {

                            hash.Add (newRect, new HashSet<int>(new List<int> () {i}));

                            hash[newRect].UnionWith (hash[key]);

                            countNew++;

                        }       

                        maxCount = Math.Max (maxCount, hash[key].Count);

                    }

                }

                if ( !bIntersect || countNew == 0 )

                    notIntersect[i] = true;                             

                if ( countNew == 0 )

                {

                    flag = true;

                    break;

                }

                Console.WriteLine ("k: " + k + " i: " + i + " Total rectangles: " + hash.Keys.Count);

                all = new List<BusyRectangle> (hash.Keys);

                all.Sort ();

​

                foreach (var key in all)

                {

                    //Console.WriteLine ("Rect: " + key.ToString() + " count: " + hash[key].Count);

                }

            }

            //??? Possible optimization 

                List<BusyRectangle> removeKeys = new List<BusyRectangle> ();

                foreach (var key in hash.Keys)

                    if ( hash[key].Count <= (k + 1) )//maxCount )//|| key.Area () < mArea )

                        removeKeys.Add (key);

                Console.WriteLine ("Keys to remove: " + removeKeys.Count);

                foreach (var rect in removeKeys)

                    hash.Remove (rect);

                //hash = hash.Where(it => it.Value.Count == (k + 1)).ToDictionary(it => it.Key, it => it.Value);

                //???

                Console.WriteLine ("2 k: " + k + " Total rectangles: " + hash.Keys.Count);

        }

        long maxArea = 0L;

        foreach (var key in hash.Keys)

        {

            if ( hash[key].Count >= K )

            {

                maxArea = Math.Max (maxArea, key.Area());

            }

        }

        return maxArea;

    }*/

    public static void Main()

    {

        /*int[] xl = new int[] { 0, -2,  0,  1,  2, 1, -3};

        int[] yl = new int[] { 0,  0,  0,  0,  0, 2, -3};

        int[] xh = new int[] { 3,  1,  3,  4,  5, 3,  7};

        int[] yh = new int[] { 2,  2,  3,  2,  1, 3 , 2};*/

        /*int[] xl = new int[] { 0,  0,  0,  0,  0};

        int[] yl = new int[] { 0,  0,  0,  0,  0};

        int[] xh = new int[] { 3,  3,  3,  3,  3};

        int[] yh = new int[] { 1,  1,  1,  1,  1};*/

        //Console.WriteLine(kRectangleIntersection (xl, yl, xh, yh, 3));

        //{{472535635, 143207838, 398752001, 102535995, 309155408, 480522905, 395449443, 331794182, 113194672, 49507477, 397277940, 138748599, 397512329, 41328148, 498876240, 196993133, 233662167, 203385491, 84861337, 321305304, 267828155, 401530676, 195843232, 279205037, 350200721, 237246800, 80970304, 146098455, 346828318, 61718298, 498948344, 372830266, 325788475, 448960428, 413739315, 407631178, 121341221, 237042226, 139898167, 465489501, 50635155, 373896652, 96791958, 121521899, 404338995, 403215683, 307310255, 191401115, 178362166, 190086327, 293732556, 225641521, 448082822, 334434299, 239370548, 231958021, 162108445, 337648455, 53027369, 72931369, 118002411, 274499770, 147842720, 225562148, 296981638, 340741305, 293138071, 228475853, 462386659, 48270520, 434537477, 60289769, 354457562, 372457557, 408910567, 339876115, 180793630, 414936863, 305009901, 217150507, 452386113, 362875678, 217378400, 262307895, 285990366, 352123740, 137785163, 53188718, 42171893, 203824036, 403640164, 80091739, 126987387, 315290468, 185427411, 247182609, 481670731, 17981978, 455516480, 118326450, 450831663, 119959963, 480959752, 107383497, 453946566, 38745783, 228473720, 427160543, 71070965, 302738944, 28145903, 183796107, 476674843, 294382156, 23590585, 106310099, 394731197, 361623543, 297979351, 228477093, 203202975, 456319245, 72114904, 253358368, 355886010, 308688062, 134099260, 87530367, 57457892, 359657245, 166486282, 206647993, 348606996, 434856850, 373096153, 482868201, 15347659, 303456428, 276754223, 88317189, 6376248, 381130480, 95539932, 43191373, 314592521, 194013346, 168860400, 298281296, 240680858, 366596190, 300669805, 210681668, 300524163, 399257449, 452184811, 171359158, 301295711, 111084332, 11719570, 84225979, 75542812, 174316733, 380392921, 385661306, 264352232, 418806122, 235919357, 252371649, 49768512, 453041164, 32704572, 249796148, 61126743, 320466066, 256776654, 304845871, 207839465, 70697586, 394152117, 208848372, 69741392, 50104816, 121622606, 221664872, 283402014, 448046360, 494270191, 211997053, 178252876, 176274158, 69233838, 100230157, 249519446, 2702332, 274676247, 86645272, 294791803, 8506842, 429880170, 245620304}, {477991443, 243627619, 109230682, 120540067, 227428744, 108477690, 316741572, 451491323, 453485043, 220885254, 352733764, 487047673, 117224300, 264761382, 221483950, 242238484, 325195622, 28763709, 378520649, 345703752, 421403375, 154358307, 145020384, 169266140, 391798484, 435797539, 316435969, 72652832, 260855641, 396758697, 475564245, 83151445, 391360627, 374452820, 245807971, 138448318, 55815680, 347343581, 486540974, 343970144, 105300183, 359262402, 57783760, 54600077, 220827786, 163656379, 131879946, 172636016, 373536969, 103327658, 272800707, 112131602, 430991672, 220316833, 438279861, 214884322, 146834705, 224745081, 74038261, 342990462, 389267363, 249251926, 183205530, 137796188, 10211765, 87705690, 64447925, 297130204, 402903447, 296034922, 382560012, 145700173, 389276884, 350840743, 261480191, 136900267, 210551721, 59201858, 167626458, 496301399, 81214812, 466742933, 272692575, 370013286, 404803256, 34089689, 298028228, 182031465, 129848226, 466722058, 118272948, 29952414, 180488154, 336827240, 418933198, 469194971, 342109413, 137003161, 413527734, 373732272, 323119124, 493319977, 72082328, 450729318, 476290812, 266511625, 347630195, 389262427, 321737618, 456690321, 27415601, 254129876, 157640935, 1247598, 322473150, 376692859, 258100001, 480674702, 98612175, 439080233, 262215581, 93598596, 92616325, 23676951, 449966756, 340898542, 176779530, 438538742, 399079842, 200128210, 135408225, 375044887, 498366403, 418472710, 353101388, 482372517, 382864656, 228203715, 150277265, 441326581, 309989258, 119165423, 261197759, 130404575, 161351428, 260592249, 251227871, 119572761, 60146810, 383944892, 336174424, 383635612, 12338699, 359998406, 257233156, 234431187, 496214900, 389988423, 393645827, 87549104, 107241038, 354109537, 182826938, 247023027, 444411891, 259902381, 383210724, 173308135, 244976810, 441096165, 192189850, 154881720, 13297923, 314797738, 231865243, 160561781, 211155875, 231380078, 342957692, 153553526, 92525919, 448304801, 85000606, 58865587, 445825951, 149194671, 17140187, 408822417, 167508656, 150013100, 56120674, 231294388, 366929635, 121471054, 498718853, 366586953, 408750052, 315476951, 319837920, 52920482}, {715281533, 998089127, 897824070, 893221920, 807408265, 967241253, 606014099, 885775069, 850827380, 901175441, 603655675, 921256453, 963673331, 987502872, 545575928, 983156896, 815895529, 962718280, 671734319, 553164163, 872544123, 886950283, 880253305, 859917430, 864384988, 764698898, 951238642, 974248839, 562927000, 639838147, 792183580, 619000273, 712433085, 662741207, 938070525, 880882771, 745232512, 712486679, 906407820, 919317000, 707711557, 944695867, 615994101, 566861452, 528638606, 526332838, 834265076, 680704156, 620705480, 901514096, 748199936, 966011724, 772752316, 939241929, 899322156, 635167374, 568274621, 751962886, 774945808, 999515401, 785698183, 901151750, 544035556, 634057757, 586228626, 829429900, 762139477, 860209708, 652440947, 993602065, 826922905, 846383473, 969138159, 584022827, 633665484, 640067518, 642439632, 816632944, 717830514, 696146186, 758349487, 882145384, 861846455, 536706437, 876162312, 552752032, 560701670, 674834912, 950054039, 833120251, 995675364, 526443020, 538096227, 868375382, 576554741, 547886307, 572190680, 732613607, 550394555, 540681097, 852366157, 820263708, 819318150, 735797864, 956601513, 818744797, 541510630, 916590859, 719712383, 974332740, 701057163, 704923827, 782417933, 572132458, 555494417, 722171224, 712947309, 578212448, 801477581, 795987028, 811955224, 693903566, 801495541, 601350063, 651841055, 880058303, 851210371, 967304375, 706370551, 533830524, 630234965, 885844936, 920997533, 961161379, 519240933, 576232524, 776984562, 707613261, 813794780, 545345683, 756079828, 848967653, 598381145, 563377841, 909456039, 572604605, 500109462, 768722684, 678388830, 528573041, 988608537, 647351695, 753842673, 527677587, 757233802, 659910967, 818691173, 939664485, 840316600, 519496609, 576706105, 918423073, 721074338, 592102811, 693398752, 697040371, 587408099, 653148876, 758144860, 924702983, 994836465, 771031114, 786961949, 889610193, 559961393, 525542444, 884342992, 748455752, 742827049, 788567745, 581485946, 567256765, 625834692, 503738937, 699083268, 545204582, 695715800, 997980074, 831290273, 693539583, 596078236, 961391721, 917999938, 989684305, 905103031, 988016011, 521968142, 545731762, 992246701, 919869754}, {576156674, 836331805, 925421192, 527316926, 890731494, 746885414, 723701804, 874363806, 907469654, 763382696, 770315056, 682100989, 809008302, 518645561, 927647837, 884266949, 735088997, 795122834, 709749415, 805096617, 586753315, 786276773, 873421194, 802028650, 582491923, 556321771, 680646953, 940786099, 641393108, 900655932, 795288523, 740315744, 867795400, 915143873, 589713044, 778598016, 763991631, 511387105, 542001046, 796055030, 708129595, 566047027, 717984741, 828857822, 973516538, 811819717, 821036429, 552005263, 845200557, 730661549, 653359915, 924706698, 537750376, 653129371, 868414089, 981178786, 729416256, 632900046, 741273915, 786607731, 849095348, 958830930, 838315835, 501803587, 799577194, 881541936, 920129724, 565041542, 816743836, 739050110, 656965680, 759526259, 686859289, 693021406, 542133735, 867442478, 623515141, 578938261, 579581891, 861983208, 642484525, 839757275, 593417569, 955046444, 757454419, 973214303, 650069526, 527473615, 504325990, 968700359, 714933848, 653426759, 571885755, 717537382, 713101197, 982536559, 857248831, 980148983, 833569225, 723479991, 739294156, 667237594, 644200910, 804012794, 989805925, 921534813, 939464287, 576930787, 542985601, 701137445, 573086154, 945429218, 843709062, 694218506, 730070674, 704833621, 659215068, 729125565, 906023019, 718319680, 801433585, 893252674, 958601815, 561750882, 810100244, 765434198, 589476200, 843822074, 716874457, 637614137, 986335152, 555047637, 967504387, 976502919, 838539406, 690203459, 988509362, 865904465, 722751789, 783704623, 851662284, 824971301, 619903687, 660782966, 539292077, 878754265, 933471526, 802287729, 503657933, 857644409, 700125794, 924105809, 748427196, 670617785, 879445971, 749269717, 697891899, 720091734, 607327157, 916312285, 852007544, 501250528, 668141357, 793966685, 845616954, 809374484, 766392385, 990520359, 856163145, 812400262, 577092030, 679130380, 630139880, 975593744, 633714287, 607257490, 963649772, 985267746, 839424686, 891471126, 867401767, 948170312, 774723616, 928213432, 584492400, 622326227, 820357954, 851567755, 561878767, 954305785, 864023607, 711640235, 842235422, 693797916, 529888698, 617116334, 875588858, 771352873, 671176376, 530344546}, 149}

​

        Random rnd = new Random (100);

        int N = 10;

        int maxValue = 100;//Int32.MaxValue;

        int[] xl = new int[N];

        int[] yl = new int[N];

        int[] xh = new int[N];

        int[] yh = new int[N];

        for (int i = 0;i < N;i++)

        {

            xl[i] = rnd.Next(0, maxValue >> 1);

            yl[i] = rnd.Next(0, maxValue >> 1);

            xh[i] = xl[i] + rnd.Next(0, (maxValue >> 1) - 1);

            yh[i] = yl[i] + rnd.Next(0, (maxValue >> 1) - 1);

        }

        int K = Math.Min (6, N - 1);//rnd.Next (1, N - 1);

        Console.WriteLine ("N: " + N + " K: " + K);

        Console.WriteLine(kRectangleIntersection (xl, yl, xh, yh, K));

    }

}

​

class BusyRectangle : IComparable

{

    public int xl { get; private set; }

    public int yl { get; private set; }

    public int xh { get; private set; }

    public int yh { get; private set; }

    //public SortedSet<int> usedRects = new SortedSet<int> ();

    public BusyRectangle (int xl, int yl, int xh, int yh)

    {

        this.xl = xl;

        this.yl = yl;

        this.xh = xh;

        this.yh = yh;

    }

    /*public void Add (int i)

    {

        usedRects.Add (i);

    }*/

    public long Area ()

    {

        return (long)(xh - xl) * (long) (yh - yl);

    }

    public override int GetHashCode ()

    {

        unchecked // Overflow is fine, just wrap

        {

            int hash = (int) 2166136261;

            // Suitable nullity checks etc, of course :)

            hash = (hash * 16777619) ^ xl;

            hash = (hash * 16777619) ^ yl;

            hash = (hash * 16777619) ^ xh;

            hash = (hash * 16777619) ^ yh;

            return hash;

        }

    }

    public int CompareTo (object obj)

    {

        if ( obj == null )

        {

                return -1;

        }

        else

        {

            BusyRectangle other = (BusyRectangle)obj;

            if ( xl < other.xl )

                return -1;

            else if (xl > other.xl )

                return +1;

            else

            {

                if ( yl < other.yl )

                    return -1;

                else if (yl > other.yl )

                    return +1;

                else

                {

                    if ( Area () < other.Area () )

                    {

                        return -1;

                    }

                    else if ( Area () > other.Area () )

                    {

                        return +1;

                    }

                    return 0;

                }

            }

        }

    }

    public override bool Equals (object obj)

    {

        if ( obj == null )

        {

                return false;

        }

        else

        {

                BusyRectangle other = (BusyRectangle)obj;

​

                if ( this.xl == other.xl && this.yl == other.yl && this.xh == other.xh && this.yh == other.yh )

                    return true;

                else

                    return false;

         }

    }

    public override string ToString ()

    {       

        return "[{" + xl + "," + yl + "}" + " {" + xh + "," + yh + "}]";

    }

}