27315번 - 틀리는 건 싫으니까 쉬운 문제에 올인하려고 합니다

한별이는 BOJ 랭킹을 올리기 위해 BOJ에서 $M$개의 문제를 풀려고 한다. 하지만 한별이는 틀렸습니다를 보는 것을 매우 싫어한다. 따라서 최소한으로 틀리면서 $M$개의 문제를 푸는 방법을 생각하기로 했다.

각 문제는 아이디어 난이도와 구현 난이도를 가진다. 아이디어 난이도가 한별이의 능력보다 높은 경우 한별이는 문제의 풀이조차 떠올릴 수 없기 때문에 문제를 풀 수 없다.

구현 난이도가 아무리 높더라도 아이디어 난이도가 한별이 아이디어 능력 이하라면 오랜 시간을 들여 문제를 푸는 것이 가능하다. 그러나 구현 난이도가 한별이의 구현 능력보다 높은 문제는 이 과정에서 $\text{구현 난이도} -\text{한별이의 구현 능력}$ 만큼 틀렸습니다를 받게 된다. 구현 난이도가 한별이의 구현 능력 이하인 문제는 틀렸습니다 없이 한번에 맞출 수 있다.

단, 데이터가 있는 문제의 경우 한별이는 데이터를 보면서 미리 답을 맞추어가기 때문에 틀렸습니다를 받지 않는다. 그리고 에디토리얼이 있는 경우, 한별이는 그 에디토리얼을 이해할 수 있으면 에디토리얼을 보며 구현을 한다. 한별이가 에디토리얼을 이해하기 위해서는 $\text{한별이의 아이디어 능력} \times 2\geq\text{문제의 아이디어 난이도}$ 이어야 한다. 에디토리얼을 보며 구현하는 경우 구현 난이도와 아이디어 난이도는 각각 $\lfloor\text{구현 난이도}/2\rfloor$, $\lfloor\text{아이디어 난이도}/2\rfloor$로 줄어든다.

문제를 $1$개씩 풀 때마다 한별이의 아이디어 능력과 구현 능력은 $1$씩 올라간다.

이때 BOJ에 있는 $N$개의 문제 가운데 $M$개를 풀 때 받아야 하는 틀렸습니다의 최솟값을 구한다. $M$개의 문제를 풀 수 없는 경우 $-1$을 출력한다.

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

다음 $N$개의 줄에 $D_i$ $P_i$ $T_i$ $E_i$의 네 정수로 각각 문제의 아이디어 난이도, 구현 난이도와 데이터 소유 여부, 에디토리얼 소유 여부가 공백으로 구분되어 주어진다.

• $1\leq D_i,P_i\leq 10^9$
• $T_i$가 $0$인 경우 데이터 없음, $1$인 경우 데이터 있음
• $E_i$가 $0$인 경우 에디토리얼 없음, $1$인 경우 에디토리얼 있음

마지막 줄에 한별이의 아이디어 능력과 구현 능력을 나타내는 정수 $HD$, $HP$가 공백으로 구분되어 주어진다. ($1\leq HD,HP\leq 10^9$)

BOJ에 있는 $N$개의 문제 가운데 $M$개를 풀 때 받아야 하는 틀렸습니다의 최솟값을 출력한다. $M$개의 문제를 풀 수 없는 경우 -1을 출력한다.