Informatica Online Judge

  광렙 [2244 / 08C4]

Time Limit(Test case) : (ms)
Number of users who solved : 12   Total Tried : 13


The Champion of this Problem (C++) : gs15120 - 0ms / 863byte
My Best Submission (C++) : N/A

[34th 정우현]
Writer ID : [gs16102]

Background

당신은 어떤 MMORPG의 네임드 플레이어다. 당신은 게임 최초로 만렙을 달성하기 위해 최대한 많은 경험치를 얻고자 한다.

이 게임에는 1번부터 n번까지 n개의 사냥터가 있고, i번 사냥터에서는 시간당 exp_i의 경험치를 벌 수 있다.

하지만, 이 게임에는 g개의 길드가 있어 i번째 길드는 d_i의 장소에서 s_i 부터 e_i 까지 사냥을 한다.

당신은 솔로플레이어이고, 모두가 당신을 경계하고 있기 때문에 다른 사람들과 같이 경험치를 벌 수는 없다.

다행히도 당신은 장거리 순간이동이 가능하여 사냥터를 마음대로 옮겨다닐 수 있고, 또 옮기는 데 걸리는 시간도 없다. 그리고 당신은 프로게이머라서 게임을 쉬지 않고 할 수 있다.

아쉽게도 잠은 자고 밥은 먹어야 해서 하루 6시간의 수면 시간, 하루 2번 1시간씩의 식사시간은 필요하다.

수면 시간은 떼어놓을 수 없지만, 하루를 넘겨 잘 수는 있다. (오후 10시~오전 4시까지 잘 수도 있다.)

그러면 이때 어떻게 해면 하루에 벌 수 있는 경험치를 최대화할 수 있을까?

Input

첫 줄에 사냥터의 개수 n(3<=n<1000)이 입력된다.
그 다음 n줄에는 i번째 사냥터의 시간당 경험치 획득량 exp_i(1<=exp_i<10000000)가 주어진다.
그 다음 줄에는 길드 수 g(1<=g<1000)이 주어진다.
그 다음 g줄에는 i번째 길드의 사냥터, 사냥시간 d_i(1<=d_i<=n), s_i, e_i(0<=s_i시간은 모두 정각으로 주어진다.
만약 d_i=1, s_i=10,e_i=14라고 하면
i번째 길드는 1번 사냥터에서 오전 10시부터 오후 2시 직전까지 사냥을 한다.

Output

당신이 하루에 벌 수 있는 경험치의 최대치를 출력한다.

IO Example

입력
5
1 2 3 5 6
6
5 4 10
5 14 15
4 14 15
5 17 18
4 17 18
3 17 18

출력
96

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]