철기는 지은이와 용평스키장에서 스키를 타고 싶어 한다. 그러나 아쉽게도 지은이는 스키를 그리 잘 타지 못한다.

그래서 지은이는 가까운 스키장에서 S(0 ≤ S ≤ 100) 스키 강좌를 신청했다. i번 강좌는 M_i(1 ≤ M_i≤ 10,000)시각에 시작하여 L_i(1 ≤ L_i≤ 10,000)시간동안 진행된다. i번 강좌이후에 지은이의 스키 능력은 정확히 A_i(1 ≤ A_i≤ 100)가 된다. A_i만큼 증가하는 것이 아니라 A_i가 된다는 점에 유의하자.

지은이는 N(1 ≤ N ≤ 10,000)개의 스키 슬로프에 대한 정보가 들어있는 지도를 구입했다.그 지도에 따르면 i번 슬로프를 이용하게 되면 스키를 타고 내려올 경우 D_i(1 ≤ D_i≤ 10,000)시간이 걸리고 슬로프에 올라 스키를 타고 내려오기 위해서는 C_i (1 ≤ C_i≤ 100) 의 스키 능력치가 필요했다. 지은이의 스키능력치가 C_i 보다 크거나 같아야 i 슬로프를 이용할 수 있다.

지은이는 T(1 ≤ T ≤ 10,000)시간이 지나면 스키장을 떠나야 한다. 마지막으로 슬로프를 내려올 때는 종료시각이 넘어서는 안된다.

지은이가 제한시간을 초과하지 않고 최대 몇 번을 탈수 있는지 구하시오. 지은이의 초기 스키능력치는 1이다.

#1497 upload 19 done 1 how_to_reg 1

지은이의 스키타기 timer 1s memory 128MB

#1497

지은이의 스키타기 1s 128MB