package BackJoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 드래곤 앤 던전
public class BOJ16434 {

    static int N, H_atk;
    static Turn[] turns;
    static long answer;

    private boolean simulate(long maxHp) {
        long curHp = maxHp;
        long atk = H_atk;

        for (Turn turn : turns) {
            int t = turn.t;
            int a = turn.a;
            int h = turn.h;

            // 전투
            if (t == 1) {
                long i = h / atk;
                long j = h % atk;
                long cnt = ((j == 0) ? (i - 1) : (i));
                curHp -= (cnt) * a;
            } else {
                curHp = (Math.min(curHp + h, maxHp));
                atk += a;
            }

            if (curHp <= 0) {
                return false;
            }
        }
        return true;
    }

    private void findAnswer() {
        long l = 1;
        long r = 123456l * 1000000l * 1000000l;

        while (l <= r) {
            long mid = (l + r) / 2;

            if (simulate(mid)) {
                r = mid - 1;
                answer = mid;
            } else {
                l = mid + 1;
            }
        }
    }

    private void solution() throws Exception{
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        N = Integer.parseInt(stringTokenizer.nextToken());
        H_atk = Integer.parseInt(stringTokenizer.nextToken());

        turns = new Turn[N];

        for (int i = 0; i < N; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());

            int t = Integer.parseInt(stringTokenizer.nextToken());
            int a = Integer.parseInt(stringTokenizer.nextToken());
            int h = Integer.parseInt(stringTokenizer.nextToken());

            turns[i] = new Turn(t, a, h);
        }

        findAnswer();


        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        new BOJ16434().solution();
    }

    static class Turn{

        int t, a, h;

        public Turn(int t, int a, int h) {
            this.t = t;
            this.a = a;
            this.h = h;
        }
    }

}

package BackJoon;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

// 피아노 체조
public class BOJ21318 {

    static int prefixSum[];
    static int N, Q;

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        String[] s = br.readLine().split(" ");
        prefixSum = new int[N + 1];
        prefixSum[1] = 0;

        for (int i = 1; i < N; i++) {
            int a = Integer.parseInt(s[i - 1]);
            int b = Integer.parseInt(s[i]);

            prefixSum[i + 1] = prefixSum[i] + ((a > b) ? 1 : 0);
        }

        Q = Integer.parseInt(br.readLine());

        for (int i = 0; i < Q; i++) {
            String[] input = br.readLine().split(" ");
            int from = Integer.parseInt(input[0]);
            int to = Integer.parseInt(input[1]);
            bw.append(prefixSum[to] - prefixSum[from] + "\n");
        }

        bw.flush();
    }

    public static void main(String[] args) throws Exception {
        new BOJ21318().solution();
    }

}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

// 민서의 응급 수술
public class Main {
    
    static int N, M;
    static int parents[];
    static int count;

	// 부모 노드(속한 집합)를 찾는 메서드 
    private int find(int node) {

        if (parents[node] < 0) {
            return node;
        }

        return parents[node] = find(parents[node]);
    }
    
    // 집합 a와 b를 합치는 메서드
    private boolean union(int a, int b){

        // 각 노드의 집합을 찾습니다.
        int pA = find(a);
        int pB = find(b);

        // 이미 같은 집합인 경우
        if (pA == pB) {
            return false;
        }

        // 다른 경우에는 집합을 합칩니다.
        parents[pA] = pB;
        return true;
    }
    

    private void main() throws Exception {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bufferedReader.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        parents = new int[N + 1];
        Arrays.fill(parents, -1);
        
        // 설명에서 1, 2의 해당하는 부분
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(bufferedReader.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            // 연결된 두 노드를 합치고, 순환이 발생한 경우 count를 하나 세줍니다.
            if (!union(a, b)) {
                count++;
            }
        }

        // 집합의 수를 저장할 변수
        int groupCnt = 0;

        // 설명에서 3에 해당하는 부분입니다. 
        // 집합의 수를 세줍니다.
        for (int i = 1; i <= N; i++) {
            if (parents[i] < 0) {
                groupCnt++;
            }
        }

        // 총 연산 수 계산
        count += (groupCnt - 1);

        System.out.println(count);
    }
}