#P3441. 乌鸦喝水

    ID: 2641 传统题 1000ms 512MiB 尝试: 606 已通过: 174 难度: 6 上传者: 标签>难度分类提高模拟与实现技巧事件驱动模拟离线与分治事件排序数据结构树状数组树状数组倍增求第 k 小CF2100Bylll6924

乌鸦喝水

乌鸦喝水

题目描述

一只乌鸦把 nn 个有魔力的水缸排成一列。它会从第 11 个水缸依次飞到第 nn 个水缸,共飞 mm 趟。每一趟都按同样的顺序访问这 nn 个水缸。

对第 ii 个水缸,初始时缸口到水面的距离为 WiW_i。每当乌鸦喝一次水,所有水缸的水位都下降,第 ii 个水缸的缸口到水面的距离增加 AiA_i。

乌鸦每次经过一个水缸时检查当时水面的深度。如果缸口到水面的距离不超过 xx,它就喝一次水。喝水是瞬间完成的,即使喝完后已经够不到这个水面,这一次仍然计入。

求乌鸦总共喝到水的次数。

输入格式

第一行包含三个整数 n,m,xn,m,x,分别表示水缸数、飞行趟数和乌鸦能达到的深度。

第二行包含 nn 个整数 W1,…,WnW_1,\dots,W_n。

第三行包含 nn 个整数 A1,…,AnA_1,\dots,A_n。

输出格式

输出一个非负整数,表示乌鸦喝水的总次数。

样例 #1

5 2 20
15 14 13 12 12
1 1 1 1 1
9

数据范围

  • 1≤n,m≤1000001\le n,m\le 100000。
  • 1≤x,Wi≤20000000001\le x,W_i\le 2000000000。
  • 1≤Ai≤2001\le A_i\le 200。