한글과 컴퓨터 학원의 원장님은 최근 N마리의 거위를 사서 기르고 계신다.

귀여운 거위들을 혼자만 보기 아까웠던 원장님은 학생들을 위해 거위 쇼를 펼치기로 했다.

성호는 원장님의 명령으로 거위 쇼에서 먹이를 주는 역할을 담당하게 되었다.

성호가 강의실에 서 있으면 강의실로 한 마리씩 거위가 들어왔다 나간다.

구체적으로 i번 거위는 T_i초에 강의실로 들어온 뒤 T_i + L 초에 강의실을 떠난다.

성호는 거위들이 강의실에 들어와 있는 아무 순간에나 먹이를 던질 수 있다.

성호가 먹이 한 개를 던지면 그 순간 강의실에 있는 거위들만 이 먹이를 먹을 수 있다.

보다 정확하게, x초에 성호가 먹이를 던지면 i번 거위는 T_i \le x \le T_i + L을 만족할 때 먹이를 먹을 수 있다.

하지만 강의실의 거위들 중에서 이를 먹을 수 있는 거위는 가장 속도가 빠른 거위 한 마리 뿐이다.

i번 거위의 속도는 A_i이고 속도는 높을 수록 빠르다. 속도가 같은 두 거위는 없다.

i번 거위가 먹이를 먹게 되면 귀여운 춤을 추기 시작한다. 이때 학생들은 C_i만큼 행복해진다.

주의할 점은 모든 거위들이 귀엽지는 않기 때문에 C_i < 0인 경우도 있다는 것이다.

먹이를 한 번 먹은 거위는 그 즉시 만족하고 강의실을 떠난다.

성호는 원하는 만큼 먹이를 마음대로 던질 수 있다.

성호의 목표는 학생들이 기분 좋아지는 양의 총합을 최대화하는 것이다.

가능한 최대 행복도의 합을 성호를 대신해 계산해보자!

거위 쇼 timer 5s memory 1024MB

거위 쇼 5s 1024MB