I - その味は甘くて Editorial /

Time Limit: 5 sec / Memory Limit: 512 MB

　突然だが，あなたはとある養蜂家専属のプログラマである．ある日，巣で生成されるハチミツの糖度を管理するために，次のようなプログラムを作成するよう求められた．

問題

　下図のような正六角形が敷き詰められた座標系を考える．
図1：正六角形が敷き詰められた座標系
　指定された座標系の上に，蜂の巣の情報が与えられる．蜂の巣は，巣のタイプと中心部の座標，および大きさから成る．巣のタイプによって，巣に含まれる六角形がどのような糖度を持つかが異なる．
    　
  • タイプ1 : 巣に含まれる全ての六角形に一様に糖度 1 が加算される．
    • 　
  • タイプ2 : 大きさを n，中心からの距離を d とすると，糖度 n-d が加算される．
    • 　
  • タイプ3 : 大きさを n，中心からの距離を d とすると，糖度 (n-d)^2 が加算される．
　
　例えば，大きさが 3 である各タイプの巣に含まれる六角形の糖度は，以下の図のように加算される．
図2：大きさ 3 の各タイプの巣
　また，六角形が複数の巣に含まれる場合は，その部分の糖度は各巣についての糖度の和になる．最大の糖度を持つ部分の糖度を出力せよ．

入力

入力は以下の形式で標準入力から与えられる． 
N
type_{1}　x_{1}　y_{1}　size_{1}
type_{2}　x_{2}　y_{2}　size_{2}
...
type_{N}　x_{N}　y_{N}　size_{N}
  • 1 行目には蜂の巣の数 N(1 ≦ N ≦ 10,000) が与えられる．
  • 2 行目～ N+1 行目には各巣の情報が 1 行ずつ与えられる．
  • 各巣の情報はタイプ( type_{i} )，中心座標( x_{i}，y_{i} )，および大きさ( size_{i} )から成り，それぞれ半角スペース区切りで与えられる．また，それぞれ以下の条件を満たす．
    • 1 ≦ type_{i} ≦ 3
    • |x_{i}| ≦ 500
    • |y_{i}| ≦ 500
    • 1 ≦ size_{i} ≦ 500

出力

最も糖度の高い六角形の糖度を1 行に出力せよ．
なお、最後には改行を出力せよ．

部分点

10 点分については，入力の条件に加え，以下の条件を全て満たす．
  • 1 ≦ N ≦ 100
  • type_{i} = 1
  • |x_{i}| ≦ 100
  • |y_{i}| ≦ 100
  • 1 ≦ size_{i} ≦ 100

50 点分については，入力の条件に加え，以下の条件を全て満たす．
  • type_{i} = 1

入力例 1

1
1 0 0 3

出力例 1

1

入力例 2

1
3 -1 -1 4

出力例 2

16
タイプ3，大きさ4の巣の最大糖度は 16 である．

入力例 3

2
1 0 0 3
3 -1 -1 4

出力例 3

17
複数の巣が重なる場合，その部分の糖度は各巣についての糖度の合計になる．

入力例 4

3
1 0 0 2
1 1 -1 2
1 -1 1 2

出力例 4

3
巣の様子は以下の図のようになる．
図3：入力例4における巣の様子