桜は春に美しい花を咲かせる、日本においては非常にポピュラーな木である。桜は大昔から日本人に愛されており、葉が出る前に花が咲くという力強さや、咲いた後に散ってゆく儚さなどその美しさの要素を挙げようと思えばきりがない。日本には、春にその桜のもとに集まって宴会を開く花見という文化がある。
さて、ある年の春、JAPLJは花見の場所取りを任された。彼はあまり積極的に行動するようなタイプの人間ではないので場所取りなどは苦手である。そこで花見が行われる場所において、他のグループが場所をどのように占有するのかを丹念に調べ上げ、その調査結果をもとに頭脳を駆使して一番よい場所を探し出すことにした。
しかし花見が行われる場所はとても広く、また花見をするグループの数もとても多い。これに対して手作業で立ち向かっていては花見までに場所取りが間に合うはずもないので、彼は調査結果をパソコンに入力し、プログラムを組んでこれを解析しようと思い立った。
花見が行われる場所を大きな長方形の広場と考え、その大きさは横が X で縦が Y であるとする。また、花見が行われる時間帯の長さを整数 T で表すとする。時刻は0以上 T 以下の実数ひとつで表され、時間は [0, T) におさまる区間で表現される。
JAPLJが所属する以外のグループは全部で M 個あり、ひとつのグループは4つの整数 x1, y1, x2, y2 と1つの区間 [s, t) で表される。これはそのグループが左下端が (x1, y1) で右上端が (x2, y2) であるような長方形を時間 [s, t) にわたって占有するということである。
JAPLJが所属するグループでは今回の花見に N 人が参加する。したがって彼は少なくとも面積が N 以上になるように場所を確保せねばならない。また確保する場所は広場の辺に平行な長方形である必要がある。他のグループに占有されている部分は当然だが場所として確保することはできないし、確保中に他のグループが自分の確保している場所に来た場合は退かねばならない。この条件のもとで、できるだけ花見を行う時間を長くしたい。つまり広場において、面積が N 以上の長方形をできるだけ長い時間確保したい。そのためのプログラムを作成せよ。
入力の最初の1行には5つの整数 X, Y (X, Y >= 1), M (M >= 1), N (1 <= N <= X*Y), T (1 <= T <= 1000000000 = 109) が書かれている。 X と Y はそれぞれ広場の横の長さと縦の長さを、 M は他のグループの数を、 N は必要な最小の面積を、 T は時刻の最大値を表す。後に M 行の入力が続く。
続く行はグループの情報を表す。各行には6つの整数 x1, y1, x2, y2, s, t が書かれており、これは問題文の通りに1つのグループを表す。
1行出力せよ。その1行には面積が N 以上の長方形の最長の確保時間の長さが書かれていなければならない。ただし時間 [a, b) の長さは b-a とする。
採点用データはいくつかのテストグループからなる。
このテストグループでは、すべてのグループの占有時間が [0, T) である。また、 X <= 100, Y <= 100, M <= 500 である。
このテストグループでは X <= 10, Y <= 10, M <= 10 である。
このテストグループでは X <= 100, Y <= 100, M <= 100 である。
このテストグループでは X <= 100, Y <= 100, M <= 500 である。
10 10 5 40 100 5 2 9 9 66 72 4 5 7 7 56 82 0 2 3 5 2 55 5 6 7 8 15 34 5 6 9 9 7 56
56
9 7 6 22 50 0 0 1 6 16 22 4 4 6 6 6 32 2 0 8 2 2 5 5 5 8 6 15 34 2 0 4 1 6 7 5 1 6 2 14 48
28