/ Vijos / 题库 /

流星雨

流星雨

背景

看流星划过夜空,并默默向流星许个心愿……在所有的天象中,流星雨该是最浪漫、最迷人的了。中科院紫金山天文台研究员说,2009年天宇将有四大流星雨适合观测。

描述

在A国的夜里,有很多人来到户外看流星雨这一天象奇观。这些人中有些是情侣,有些仅仅是普通的同学。由于流星姐姐生气了,她决定只想在边长为f*f的区域内释放流星雨。A国的地图可以看成是一个边长为n*n区域。每个位置可能有四种情况:没有人、只有情侣、只有同学、既有情侣又有同学。让一个单位的同学看到流星雨可以增加a点Rp,让一个单位的情侣看到流星雨可以增加b点Rp。Rp的初始值为0。输出可以得到最大的Rp值。

格式

输入格式

第一行4个整数n,f,a,b
第二行1个整数k。

以下k行,每行4个整数,x,y,x1,y1表示纵坐标为x,横坐标为y的地点增加了x1个单位的情侣,y1个单位的同学。(一开始没一个人也没有人)

改成
以下k行,每行4个整数,x,y,x1,y1表示纵坐标为x,横坐标为y的地点增加了x1个单位的同学,y1个单位的情侣。(一开始没一个人也没有人)

输出格式

一个整数,为可以达到的最大Rp值。

样例1

样例输入1

4 2 1 3
3
2 2 1 3
2 3 4 5
3 2 3 4

样例输出1

44

限制

所有测点1s。

提示

F<=N<=1500000
k <= 10000

来源

小涵包生日快乐哈!
1s、milk_nzk、玛维-影之歌为流星雨和所有OI的幸福赶制。

信息

ID
1619
难度
7
分类
数据结构 | 线段树 点击显示
标签
(无)
递交数
352
已通过
62
通过率
18%
被复制
1
上传者

相关

在下列训练计划中:

RP++分类题库