Description

You are playing a game. The goal of this game is to kill the monster when you are still alive (HP > 0, HP = health point). The monster is dead if and only if its HP <= 0.

This game consists of rounds, and you go first in each round.

You have 3 options in each round:

1. ATTACK. This will deduct the monster's HP. If your damage point is p, then you can deduct p monster's HP.
2. HEAL. You can recover some of your HP, but it can't exceed your max HP.
3. Level-up. Level-up might enhance the effect of attacking or healing, but if you are not lucky enough, sometimes it will deduct the effect of attacking and healing. Thus, choosing to level-up is not always a good choice. If you have reached max level, taking this action makes no effect.

In each round, the monster will attack you once with a fixed amount of damage points.

You start the game with full HP and level 1. What is the minimun number of rounds you need to kill the monster?

Input

First line contains 4 numbers L, HP, MHP, MDMG.

• L = max level
• HP = your max HP
• MHP = monster's HP in the beginning of game
• MDMG = monster's damage point

Each of the next L lines describes each level, i-th line of them describing level i. Each of them consists of two numbers, DMG and HL.

• DMG = your damage point when you use ATTACK at level i
• HL = amount of HP you can recover when you use HEAL at level i

Limits:

• L <= 15
• HP <= 300
• MHP <= 400
• MDMG <= 10000
• DMG <= 10000
• HL <= 50

Output

Print a single integer, denoting the mininum number of steps you need to kill the monster.

If you are unable to beat the monster, print -1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Download the C++ reference.
You will see the file named "12534.cpp" but that's OK.
Just download the file and change the filename extension(副檔名) into "zip" then you can upzip the file and use the reference.
The link is below.

reference.zip

Input

Output

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Given a sequence A = a₁, a₂, ..., a_N.

A continuous subsequence A[L ... R] = a_L, ..., a_R of  A is called very beautiful if every element in A[L...R] is unique.

There will be Q queries.

In the i-th query, you'll be given L_i and R_i and you have to find the minimum number of elements needed to be removed to make the subsequence A[L_i...R_i] very beautiful.

It is guaranteed for each i = 1, 2, ..., Q - 1, L_i ≤ L_i+1 and R_i ≤ R_i+1.

For example, if A = [1, 3, 3, 4, 1] and L = 1, R = 5.

You can remove A[1] and A[3] to make A very beautiful.

On the other hand, removing one element is not enough to make A very beautiful.

Hence, the minimum number of elements needed to be removed is 2 in this example.

It is recommended to include<stdio.h> and use scanf/printf instead of cin/cout to speed up input and output.

You may need to select c++11, c++14, c++17 as the compiler to avoid compile error.

Input

The first line of the input contains an integer T, the number of testcases.

The first line of each testcase contains two integers N Q, the length of A and the number of queries.

The second line of each testcase contains N integers, a₁, a₂, ..., a_N.

Each of the next Q lines contains two integers L_i R_i, the subsequence you are queied.

For each test,

1. N ≤ 100, Q ≤ 100
2. N ≤ 100, Q ≤ 100
3. N ≤ 1000, Q ≤ 1000
4. N ≤ 1000, Q ≤ 1000
5. N ≤ 200000, Q ≤ 100000
6. N ≤ 200000, Q ≤ 100000

T ≤ 10, 1 ≤ a_i ≤ 10⁹, 1 ≤ L_i ≤ R_i ≤ N.

Output

For each query in each testcase, please print the minimum number of element needed to be removed to make the subsequence very beautiful.

You have to print an extra new line at the end of each testcase, including the last one.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are N bars line up in a row. The height of the i-th bar is h_i, and the width of each bar is 1. Please find the largest rectangle in it. 

Sample test:

Input

The first line has an integer T, means there are T testcases.

The first line of each testcase contains an integer N, and the second line contains N integers h₁ ~ h_N.

1 <= h_i <= 1e9.

1 <= T <= 10.

In testcase 1 ~ 4: 1 <= N <= 1000.

In testcase 5 ~ 8: 1 <= N <= 2e5.

Output

Please print the area of the largest rectangle for each testcase.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

It is now the year 2023, and the CS student association is going to throw a dance party once again. On the whole, the rules are quite similar to the ones in 13532 - Promenade Dance, where the objective was to avoid crisscrossed ribbons and maximise the number of paired couples.

However, there are some changes this year. First and foremost, each boy is able to know the exact name of the girl he had invited (at least in most cases).

What's more, the CS student association measured the happiness value, i.e., the amount of disappointment if one is not selected and the amount of happiness if one is selected, of each boy. Since we would like to make the atmosphere of the party cheerful and see fewer people upset, we shall select the pairs in such a way that the sum of their happiness values is maximum.

Input

There's an integer \(N\) in the first line, indicating the number of boys / girls. The second line consists of \(N\) strings \(B_i\) which are the names of girls invited by \(i^\text{th}\) boy. The third line are \(N\) strings \(G_i\) which are the names of girls . The last line would be \(N\) integers \(W_i\) representing the happiness values. For the sake of your simplicity, they would come in the same order as the girls the boys have invited.

It is guaranteed that the names consist only of English letters and numbers, have a length of at most 10, and are unique, and that \(B\) is a permutation of \(G\) and \(N<10^6\).

• In 40% of the testcases, the happiness values are always 1 and the names of girls' are \(1,2\dots N\). Alhough this sounds peculiar, you might consider this subtask is well-nigh identical to 13532 - Promenade Dance.
• In another 40% of the testcases, the happiness values are still always 1. You could solve this subtask as well probably if you could solve 13532 - Promenade Dance with some slight extra codes.
• In the last 20% of the testcases, the happiness values varies. It may be far more challenging.

Output

Please print out the maximum sum of happiness values we could select.

Explanation

Let's take above figure as instance. Suppose that boys had invited Leia, Padmé, Jyn, Rey, Rose & Dormé, respectively, and the girls are Leia, Dormé, Padmé, Jyn, Rose & Rey sequentially.

If the happiness values of 6 boys are all 1, then this circumstance is reduced to the sample in 13532 - Promenade Dance. In this case, we should select Leia, Padme, Jyn & Rey (or one may select Leia, Padme, Jyn & Rey alternatively), resulting an the answer of 4.

On the other hand, if the happiness values of 6 boys are 1, 9, 3, 3, 1 & 1, respectively, then the optimal selection would be Leia & Dormé and the answer is thus \(1+9=10\), whereas the original selection would yield a sum of \(1+3+3+1=8\).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

1. Only C and C++ are allowed. Solving problems with other languages (e.g. python, java) are forbidden, otherwise you'll get zero point.

2. Paper references, electronic devices, or other items that may contain any information relative to this exam are not allowed.

3. Before leaving, please tell TAs, we'll check if your accepted / partially accepted submissions are all written in C  or C++. After you pass the check, you may sign your name as a record and leave.

4. The score of each problem is shown below:

   • 12306: 25 points

   • 13514: 25 points

   • 13928: 25 points

   • 13933: 25 points

If you get partially correct in a problem, your score of the problem will be

• score of the problem * number of testcases you passed / number of testcases

For example, if score of a problem is 10 points and the problem contains 6 testcases. If you pass the 3 testcases, you'll get 10*3/6=5 points on this problem.

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss