시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 103 43 33 45.833%

문제

인물이와 정수는 친한 친구이다. 어느 날 인물이가 하는 게임에 관심이 생긴 정수는 게임에 대해 이것저것 물어보았다.

게임에는 N마리의 몬스터가 있고, M마리의 몬스터를 잡으면 이 게임을 클리어하게 된다. 몬스터는 한 번에 하나씩만 잡을 수 있다.

각각의 몬스터를 잡으면 그 몬스터가 주는 아이템을 얻을 수 있다. 즉 a번 몬스터를 잡으면 a번 아이템을 얻을 수 있고, a번 아이템을 다른 경로로 얻을 수 있는 방법은 없다.

게임을 많이 했던 인물이는 각 몬스터들을 한 번씩 잡아서 모든 아이템을 갖고 있다. 그래서 인물이는 각 몬스터의 난이도가 Ci라고 했지만, 정수는 게임을 처음 해서 아이템이 없기 때문에 그보다 더 어려워질 수 있다.

인물이는 정수에게 권장 아이템에 관한 팁 p개를 알려주었다. 팁은 a, b, t의 형태를 갖고 있고, a 아이템 없이 b 몬스터를 잡을 경우 t 만큼 어려워진다는 것을 말한다.

정수는 게임을 하면서 만나는 몬스터의 최대 난이도를 이 게임의 난이도라고 생각한다. 인물이는 정수가 게임을 너무 어렵게 느끼지 않도록 몬스터를 잡는 순서를 잘 정해주었다. 정수가 게임을 클리어할 때 느끼는 난이도를 최대한 줄여보자.

입력

첫 번째 줄에 두 정수 N,이 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)

두 번째 줄에 N 개의 정수 C1, C2, ... , CN 가 공백으로 구분되어 주어진다. Ci 은 인물이에게 i 번째 몬스터의 난이도를 말한다. (1 ≤ Ci ≤ 1,000,000,000)

세 번째 줄에 정수가 받은 팁의 개수 p 가 주어진다. (0 ≤ p ≤ 300,000)

다음 p 줄에 걸쳐 a, b, t 가 주어진다. a 아이템이 없어 b 몬스터를 잡을 때 t 만큼 난이도가 올라가게 된다. (1 ≤ a, b ≤ N, 1 ≤ t ≤ 1,000,000,000)

두 팁의 a, b가 같은 경우는 주어지지 않는다.

출력

정수가 게임을 클리어할 때 느끼는 난이도의 최소값을 출력한다.

예제 입력 1

5 3
2 1 5 6 3
0

예제 출력 1

3

예제 1의 경우 권장 아이템 없이 자유롭게 몬스터를 잡을 수 있다. 따라서 1, 2, 5번째 몬스터를 잡으면 클리어할 수 있고, 이때 난이도는 3 이다.

예제 입력 2

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

예제 출력 2

4

예제 2의 경우 4번 아이템 없이 2번 몬스터를 잡으면 3만큼 난이도가 올라간다. 이때 1, 2, 5번째 몬스터를 잡으면 각각 난이도가 2, 4, 3 이다. 따라서 이때 게임의 난이도는 4 이다. 이것이 클리어하는 모든 경우 중 최소값이라는 것은 쉽게 알 수 있다.

출처

University > 경인지역 6개대학 연합 프로그래밍 경시대회 > shake! 2020 B번