인물이와 정수

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

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

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

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

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

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

첫 번째 줄에 두 정수 N, M 이 공백으로 구분되어 주어진다. (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가 같은 경우는 주어지지 않는다.

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