Simulate an Account Balance

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

An account starts with a non-negative integer balance $B$. Process $n$ commands in input order. Each command has an integer code $c$ and a non-negative integer amount $x$. Code $1$ deposits $x$. Code $2$ withdraws $x$ if the current balance is at least $x$; otherwise the withdrawal fails, leaves the balance unchanged, and increases the failure count by one. A zero withdrawal always succeeds. Output the final balance and the number of failed withdrawals.

Input

The first line contains integers $B$ and $n$. Each of the next $n$ lines contains an integer code $c$ and amount $x$ in processing order; $c$ is either $1$ or $2$.

Output

Print two integers separated by one space: the final balance and the failed-withdrawal count.

Subtasks

• Subtask 1 (20%): $0\le B,x\le 1000,\ 0\le n\le 20$.
• Subtask 2 (30%): $0\le B,x\le 10^6,\ 0\le n\le 1000$.
• Subtask 3 (50%): $0\le B,x\le 10^9,\ 0\le n\le 100000$.

Examples

Example 1

Input:

10 5
2 6
2 5
1 7
2 11
2 1

Output:

0 2

Explanation: Start at balance 10 and zero failures. Withdraw 6: balance 4. Withdraw 5: failure 1, balance 4. Deposit 7: balance 11. Withdraw 11: balance 0. Withdraw 1: failure 2, balance 0. Print 0 2.

Example 2

Input:

0 3
2 0
2 1
1 0

Output:

0 1

Explanation: Withdrawing zero at zero balance succeeds. Withdrawing 1 fails, and depositing zero changes nothing. The answer is 0 1.

Example 3

Input:

25 0

Output:

25 0

Explanation: There are no commands. The balance stays 25 and there are zero failures.